# Check if two trees are identical

The idea is simple: two trees are identical if:

- Current node has the same key
- Left subtrees are identical
- 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