Introduction to Data Structures and Algorithms

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

I would not dive into a lot of coding in this blog. Prof Naveen Gargs’ lectures are enough for this blog post. Have a go at the lecture:

The transcript of the lecture can be found over here:
http://textofvideo.nptel.iitm.ac.in/1074/lec1.pdf

For the Python code of the Insertion Sort algorithm, please refer to my blog post on Insertion Sort.
https://codeatsociallywired.wordpress.com/2013/07/06/insertion-sort-and-shell-sort-the-two-brothers/

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"