Check if two trees are identical

23.04.2015

The idea is simple: two trees are identical if:

  1. Current node has the same key
  2. Left subtrees are identical
  3. Right subtrees are identical

The code builds up from any tree traversal algorithm (inorder/preorder/postorder) where you check if the tree is not empty, plus:

1) we must return True when both nodes are None, because it means they reached the same leaf at the same time;

2) if they’re not both nodes (first if) and they’re not both None (second if), it means one is a node and one is None; therefore the two trees must be different (one has at least one extra node), and we return False.

1
2
3
4
5
6
7
8
9
10
def identical(t1, t2):
    if t1 and t2:
        return t1.key == t2.key
               and identical(t1.left, t2.left)
               and identical(t1.right, t2.right)
 
    if t1 is None and t2 is None:
        return True
 
    return False
|