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"