# 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
```

# 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"

```

# Preorder Traversal of Binary Tree

Here is the code for iterative preorder traversal of binary trees.

```
'''class implementing binary tree'''
'''Binary Tree Class and its methods'''
class BinaryTree:
def __init__(self, root):
self.root = root #root node
self.leftChild = None #left child
self.rightChild = None #right child

#set root node
def setRoot(self, root):
self.root = root
#get root node
def getRoot(self):
return self.root
#get left child of a node
def getLeftChild(self):
return self.leftChild
#get right child of a node
def getRightChild(self):
return self.rightChild
#insert a left child of a node
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
#insert a right child of a node
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

#recursive function for inorder traversal of binary tree
def preOrderTraversalRecursive(tree):
if tree == None:
return
else:
print tree.root
preOrderTraversal(tree.leftChild)
preOrderTraversal(tree.rightChild)

#iterative function for inorder traversal of binary tree
def preOrderTraversalIterative(tree)
stack = []
if tree == None:
return
stack.append(tree)
while(stack != []):

node = stack.pop()
print node.root
if node.getRightChild():

stack.append(node.getRightChild())

if node.getLeftChild():
stack.append(node.getLeftChild())

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 "Preorder traversal of tree recursively is:", preOrderTraversalRecursive(r)
print "\n\n"
print "Preorder traversal of the tree iteratively is:", preOrderTraversalIterative(r)
print "\n\n"
```

# Inorder Traversal Of Binary Tree

Although recursion is a very easy way of traversing through Binary Tree but it can easily cause memory problems. The iterative solution can be handy in such cases. A very good explanation of iterative inorder traversal of Binary Tree can be found in the following video produced by Saurabh.

I have implemented using python.

```
'''Binary Tree Class and its methods'''
class BinaryTree:
def __init__(self, root):
self.root = root #root node
self.leftChild = None #left child
self.rightChild = None #right child

#set root node
def setRoot(self, root):
self.root = root
#get root node
def getRoot(self):
return self.root
#get left child of a node
def getLeftChild(self):
return self.leftChild
#get right child of a node
def getRightChild(self):
return self.rightChild
#insert a left child of a node
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
#insert a right child of a node
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t

#recursive function for inorder traversal of binary tree
def inOrderTraversalRecursive(tree):
if tree == None:
return
else:
inOrderTraversal(tree.leftChild)
print tree.root
inOrderTraversal(tree.rightChild

#iterative function for inorder traversal of binary tree
def inOrderTraversalIterative(tree)
current = tree
stack = []
done = True

while(done):
if current:
stack.append(current)
current = current.getLeftChild()
else:
if stack == []:
done = True
else:
current = stack.pop()
print current.root
current = current.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 "Inorder traversal of tree recursively is:", inOrderTraversalRecursive(r)
print "\n\n"
print "Inorder traversal of the tree iteratively is:", inOrderTraversalIterative(r)
print "\n\n"

```

# Binary Trees

This post explains binary tree and implements it in python.

```
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

'''pre order traversal of binary trees'''
def preOrderTraversal(tree):
if tree == None:
return
else:
print tree.root
preOrderTraversal(tree.leftChild)
preOrderTraversal(tree.rightChild)

'''Inorder traversal of binary trees'''
def inOrderTraversal(tree):
if tree == None:
return
else:
inOrderTraversal(tree.leftChild)
print tree.root
inOrderTraversal(tree.rightChild)

'''Post order traversal of binary trees'''
def postOrderTraversal(tree):
if tree == None:
return
else:
postOrderTraversal(tree.rightChild)
postOrderTraversal(tree.leftChild)
print tree.root

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

'''Finding the maximum Element of a binary Tree'''
maximumEle = 0
def maximumElement(tree):
global maximumEle
if tree == None:
return
else:
if tree.root > maximumEle:
maximumEle = tree.root
maximumElement(tree.leftChild)
maximumElement(tree.rightChild)

if __name__ == "__main__":
r = BinaryTree(5)
print "The root of the tree is", r.getRoot()
r.insertLeftChild(6)
r.insertRightChild(7)

#print r.leftChild.root
#print r.rightChild.root

r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)

r.rightChild.insertRightChild(63)

print "Preorder traversal of the tree is:", preOrderTraversal(r)
print "\n\n"

print "Inorder traversal of the tree is:", inOrderTraversal(r)
print "\n\n"

print "Post order traversal of the tree is:", postOrderTraversal(r)
print "\n\n"

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

maximumElement(r)
print "Maximum element of the tree is", maximumEle

```