Recursive Tree Comparison
Compare the current node, then recursively compare left and right subtrees.
0 of 4 problems solved
Recursive Tree Comparison
Compare the current node, then recursively compare left and right subtrees.
- •Are two trees equal only if current nodes, left subtrees, and right subtrees all match?
- •Is recursion the cleanest way to compare the same shape repeatedly?
- •Do I handle null vs non-null immediately?
Tree comparison works best recursively because the same rule repeats everywhere. Two trees are the same only if the current nodes match, the left subtrees match, and the right subtrees match. That means each recursive call is doing one tiny comparison and delegating the rest down the branches.
'Same tree' is really three checks repeated over and over: node, left, right.
- 1If both nodes are null, they match.
- 2If one is null and the other is not, they fail.
- 3If both exist but values differ, they fail.
- 4Otherwise recursively compare left children and right children.
Checking only the current node values misses shape differences deeper in the tree.
Symmetric Tree
DFS with two pointers starting at root. At each step compare left.left with right.right and left.right with right.left simultaneously.
Serialize and Deserialize Binary Tree
BFS serialization: write each node value or 'null' separated by commas. Reconstruct by replaying a queue of pending parent nodes.