Check if two trees are identical

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.

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