A Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child and the top-most node in the tree is called the root.
By far, the most common interview question at companies like Facebook, Amazon, Netflix, and Google is to clone (or compare) two binary trees. This largely involves the same process. Let's look at an example, comparing two binary trees.
ALGORITHM OVERVIEW: sameTree(tree1, tree2) 1. If both trees are empty then return 1. 2. Else If both trees are non -empty (a) Check data of the root nodes (tree1->data == tree2->data) (b) Check left subtrees recursively i.e., call sameTree( tree1->left_subtree, tree2->left_subtree) (c) Check right subtrees recursively i.e., call sameTree( tree1->right_subtree, tree2->right_subtree) (d) If a,b and c are true then return 1. 3 Else return 0 (one is empty and other is not)
# Python program to determine if two trees are identical # A binary tree node has data, pointer to left child # and a pointer to right child class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # Given two trees, return true if they are structurally # identical def identicalTrees(a, b): # 1. Both empty if a is None and b is None: return True # 2. Both non-empty -> Compare them if a is not None and b is not None: return ((a.data == b.data) and identicalTrees(a.left, b.left)and identicalTrees(a.right, b.right)) # 3. one empty, one not -- false return False # Driver program to test identicalTress function root1 = Node(1) root2 = Node(1) root1.left = Node(2) root1.right = Node(3) root1.left.left = Node(4) root1.left.right = Node(5) root2.left = Node(2) root2.right = Node(3) root2.left.left = Node(4) root2.left.right = Node(5) if identicalTrees(root1, root2): print "Both trees are identical" else: print "Trees are not identical" # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
Complexity of the identicalTree() will be according to the tree with lesser number of nodes. Let number of nodes in two trees be m and n then complexity of sameTree() is O(m) where m < n.
Want study questions delivered to your inbox?