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.