Binary.py

__author__ = "Ayush Shah, Harshit Bhatt"
__email__ = "ayushcshah@gmail.com"

class BinaryTree:
    def __init__(self, root):
        self.right = None
        self.left = None
        self.root = root

    def insertLeft(self, node):
        if self.left is None:
            self.left = BinaryTree(node)
            return self.left
        else:
            print "left node present"

    def insertRight(self, node):
        if self.right is None:
            self.right = BinaryTree(node)
            return self.right
        else:
            print "right node present"


def get_inorder_subtrees(tree):

    global inordersubtree

    if (tree.left is None) and (tree.right is None):
        return tree.root
    temp = ""

    if tree.left is not None:
        temp = get_inorder_subtrees(tree.left)

    temp = temp + tree.root # Left, Root, Right

    if tree.right is not None:
        temp = temp + get_inorder_subtrees(tree.right)

    inordersubtree.append(temp)

    return temp


def get_postorder_subtrees(tree):

    global postordersubtree
    if (tree.left is None) and (tree.right is None):
        return tree.root
    temp = ""

    if tree.left is not None:
        temp = get_postorder_subtrees(tree.left)

    if tree.right is not None:
        temp = temp + get_postorder_subtrees(tree.right)

    temp = temp + tree.root # Left, Right, Root

    # Append postorder traversal of each subtree.
    postordersubtree.append(temp)

    return temp

def isDuplicateSubtreesPresent(tree):

    get_inorder_subtrees(tree)
    get_postorder_subtrees(tree)

    dic = {}

    for inorder, postorder in zip(inordersubtree, postordersubtree):
        if inorder + "-" + postorder in dic:
            print "Duplicate Subtrees present"
            return True
        else:
            dic[inorder + "-" + postorder] = "Tree"
    return False

def genTree():
    a = BinaryTree('A')

    b = a.insertLeft('B')
    c = a.insertRight('C')

    d = b.insertLeft('D')
    e = b.insertRight('E')

    d.insertLeft('G')
    d.insertRight('H')

    e.insertRight('F')

    X1 = c.insertLeft('X')
    D2 = c.insertRight('D')

    E1 = X1.insertRight('E')

    E1.insertRight('F')

    D2.insertLeft('G')
    D2.insertRight('H')

    return a

if __name__ == "__main__":

    #     Used for saving inorder and postorder traversals of subtree.
    inordersubtree = []
    postordersubtree = []

    # Generate Tree with duplicate subtrees
    tree = genTree()

    isDuplicateSubtreesPresent(tree)