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