# 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