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) 

Time Complexity:
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?

Subscribe

Get CrunchSkills in your inbox weekly. Stay sharp for your next technical interview.