Recursion and Trees
Combining what the children return
Measuring a tree, and walking two trees in step.
Key idea
Measuring downward
Some measurements are about how far the tree extends. The pattern is the same template, with a combination that takes the larger or smaller of the two children's answers and adds the current node.
Key idea
Walking two trees at once
The second kind of combination takes two trees and recurses on both in step: left against left, right against right. The base cases multiply, and getting them right is the whole difficulty.
There are three: both empty, exactly one empty, and both present. The middle case is the one people forget, and it is what stops the recursion from raising on a missing child.
Gotcha
The order of the two base cases matters
Check both-empty first, then either-empty. Reversed, the either-empty test fires when both are None and wrongly reports a mismatch.
This is the same left-to-right evaluation care as the stack guards in U4, and the same fix: order the conditions so the more specific one is tested first.
Tip
The second example is worth studying
T(1, T(2)) has a left child. T(1, None, T(2)) has a right child. Both hold the same values and both have two nodes, and they are different trees.
Any function comparing two trees has to compare structure, not just contents, and pairing left with left and right with right is what does that. Comparing left against right somewhere by accident produces a function that reports mirrored trees as identical.
What comes next
The two problems below are these two shapes exactly. One measures how deep the tree goes, the other compares two trees node by node.
Both are short. Get the base cases right and there is nothing else to them, which is why they arrive here rather than later.
How many base cases?
You are writing a function that compares two trees for equality of both structure and values. How many base cases does it need before the recursive step?
Maximum Depth Of Binary Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Same Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.