# Trees

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

Here is the lecture on general trees and binary trees by Prof Naveen Garg.

Some very important properties of a binary tree assuming that the height of the tree is h are:

1. The maximum number of nodes at each level of a binary tree is: 2l where l is the level number.

2. The number of nodes n in a full binary tree are: 2h+1-1
This is because a binary tree of height h has h levels. So we add the number of nodes at each level
(20+21+22…2h)

3. The number of leaf nodes in a full binary tree is: 2h

Here is the python implementation of a binary tree:

```class BinaryTree:
#binary tree constructor
def __init__(self, root):
self.root = root
self.leftChild = None #initializing left child of a binary tree
self.rightChild = None #initializing right child of a binary tree

#method for setting the root of a binary tree
def setRoot(self, root):
self.root = root

#method for getting the root of a binary tree
def getRoot(self):
return self.root

#method for getting the left child of the binary tree
def getLeftChild(self):
return self.leftChild

#method for getting the right child of the binary tree
def getRightChild(self):
return self.rightChild

#method for inserting the left child of the binary tree
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

#method for inserting the right child of the binary tree
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
```
Advertisements

# Identical Binary Trees

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

def isStructurallyIdentical(tree1,tree2):
if tree1 == None and tree2 == None:
return True
if tree1 == None or tree2 == None:
return False

return (tree1.root == tree2.root and isStructurallyIdentical(tree1.getLeftChild(), tree2.getLeftChild()) and isStructurallyIdentical(tree1.getRightChild(), tree2.getRightChild()) )

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

t = BinaryTree(5)
t.insertLeftChild(6)
t.insertRightChild(7)
t.leftChild.insertLeftChild(12)
t.leftChild.insertRightChild(54)
t.rightChild.insertRightChild(63)

print isStructurallyIdentical(t,r)
```

# Number of Leaves, Non Leaf Nodes and Nodes having one Child of a Binary Tree

```
class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

def getNumberOfLeavesIterative(tree):
queue = []
leafCount = 0
queue.append(tree)

if tree == None:
return 0

while (queue != []):
temp = queue.pop(0)
if temp.getLeftChild() == None and temp.getRightChild() == None:
leafCount += 1

if temp.getLeftChild():
queue.append(temp.getLeftChild())

if temp.getRightChild():
queue.append(temp.getRightChild())

return leafCount

def getNumberOfNonLeafNodesIterative(tree):
queue = []
nonleafCount = 0
queue.append(tree)

if tree == None:
return 0

while (queue != []):
temp = queue.pop(0)
if temp.getLeftChild() != None and temp.getRightChild() != None:
nonleafCount += 1

if temp.getLeftChild():
queue.append(temp.getLeftChild())

if temp.getRightChild():
queue.append(temp.getRightChild())

return nonleafCount

def getNumberOfNodesHavingOneChild(tree):
queue = []
oneChildCount = 0
queue.append(tree)

if tree == None:
return 0

while (queue != []):
temp = queue.pop(0)
if (temp.getLeftChild() == None and temp.getRightChild() != None) or(temp.getLeftChild() != None and temp.getRightChild() == None) :
oneChildCount += 1

if temp.getLeftChild():
queue.append(temp.getLeftChild())

if temp.getRightChild():
queue.append(temp.getRightChild())

return oneChildCount

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "The number of leaf nodes of the binary tree are:",getNumberOfNonLeafNodesIterative(r)
print "\n\n"

print "The number of non-leaf nodes of the binary tree are:", getNumberOfNonLeafNodesIterative(r)
print "\n\n"

print "The number of nodes having just one child are:", getNumberOfNodesHavingOneChild(r)
print "\n\n"

```

# Level Order Traversal of Binary Tree and Reverse Level Order Traversal

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

'''Iterative Level Order Traversal of a Binary Tree'''
def iterativeLevelOrderTraversal(tree):
current = tree
queue = []
queue.append(current)
while (queue != []):
temp = queue.pop(0)
print temp.root
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())

'''Printing Level Order Traversal in a reverse way'''
def printingLevelOrderReverse(tree):
stack = []
if tree == None:
return 0
else:
queue = []

queue.append(tree)
while(queue != []):
temp = queue.pop(0)
stack.append(temp.root)
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())

if stack != []:
for i in range(len(stack)):
print stack.pop()
else:
return 0

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "Levelorder traversal of the tree is:", iterativeLevelOrderTraversal(r)
print "\n\n"

print "Printing level order in a reverse way:", printingLevelOrderReverse(r)
print "\n\n"

```

# Size and Height of a Binary Tree

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

'''recursive process for finding height of a binary tree'''
def height(tree):
if tree == None:
return 0
else:
return max(height(tree.leftChild),height(tree.rightChild)) + 1

'''iterative process for finding height of a binary tree'''
def heightIterative(tree):
height = 0
if tree == None:
return 0

queue = []
queue.append(tree)
queue.append("NULL")

while ( queue != []):
root = queue.pop(0)
if root == "NULL":
if queue != []:
queue.append("NULL")
height += 1
else:
if root.getLeftChild():
queue.append(root.getLeftChild())
if root.getRightChild():
queue.append(root.getRightChild())

return height

'''recursive process for finding size of a binary tree'''
def size(tree):
if tree == None:
return 0
else:
return size(tree.getLeftChild()) + 1+ size(tree.getRightChild())

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "Height of the tree is:", height(r)
print "\n\n"

print "size of the tree is:", size(r)
print "\n\n"

print "height of the tree is:", heightIterative(r)
print "\n\n"

```

# Searching an Element in a Binary Tree

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

'''Recursive method for searching an element in a tree'''
def searchingElementRecursive(tree,element):
if tree == None:
return False
else:
if tree.root == element:
return True
else:
temp = searchingElementRecursive(tree.leftChild,element)
if temp != 0:
return temp
else:
return searchingElementRecursive(tree.rightChild,element)

'''Iterative method for searching an element in a tree'''
def searchingElementIterative(tree,element):
queue = []
#    current = tree
queue.append(tree)

if tree == None:
return False

while (queue != []):
temp = queue.pop(0)
if temp.root == element:
return True

if temp.getLeftChild():
queue.append(temp.getLeftChild())

if temp.getRightChild():
queue.append(temp.getRightChild())

return False

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "Search for element 63", searchingElementRecursive(r,63)
print "\n\n"

print "Search for element 36", searchingElementRecursive(r,36)
print "\n\n"

print "Search for element 63", searchingElementIterative(r,63)
print "\n\n"

print "Search for element 36", searchingElementIterative(r,36)
print "\n\n"
```

# Maximum Element in A Binary Tree

```class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None

def setRoot(self, root):
self.root = root

def getRoot(self):
return self.root

def getLeftChild(self):
return self.leftChild

def getRightChild(self):
return self.rightChild

def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t

def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

'''recursive way to find the maximum element of a tree'''
def maximumElement(tree):
max = 0
if tree == None:
return
else:
rootValue = tree.root
left = maximumElement(tree.leftChild)
right = maximumElement(tree.rightChild)

if left > right:
max = left
else:
max = right

if rootValue > max:
max = rootValue

return max

'''iterative way to find the maximum element of a tree'''
def maximumElementIterative(tree):
queue = []
current = tree
max = 0
queue.append(tree)

if tree == None:
return 0
else:
while (queue != []):
temp = queue.pop(0)
if max <= temp.root:
max = temp.root
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
return max

if __name__ == "__main__":

r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)

print "The maximum element in the tree recursively is:", maximumElement(r)
print "\n\n"

print "The maximum element in the tree iteratively is:", maximumElementIterative(r)
print "\n\n"

```