What is bottom-up recursion?
In a bottom-up traversal each call first recurses into both children, waits for their return values, then combines them into its own answer and returns that upward. Nothing is decided until the subtrees report back.
This is the natural shape for anything defined in terms of subtree results: height (1 + max of child heights), whether a subtree is balanced, node/leaf counts, subtree sums. It is exactly a postorder walk: left, right, then act on the node.
// bottom-up: children return, parent combines
solve(node):
if node == null: return base
L = solve(node.left)
R = solve(node.right)
return combine(L, R, node.val)
solve(node):
if node == null: return base
L = solve(node.left)
R = solve(node.right)
return combine(L, R, node.val)
Time Complexity
O(N)
Each node returns exactly once; the combine step is O(1) per node.
Space Complexity
O(H)
Recursion stack depth equals the tree height H (O(N) if skewed).
Live Visualization
Current call
On active path
Returned a value
Fails condition
Call stack (top = current) — a frame returns once both children report back
Returned values (per node)
node = –
L = –
R = –
return = –
Step 0 / 0
Current node
–
being processed
Left returns
–
child result
Right returns
–
child result
This returns
–
combined
Pick a mode and hit Play to watch answers bubble up from the leaves.
✓ Done
Speed
Step-by-step trace
| # | Action | Node | L | R | Returns |
|---|
C++ — Maximum Depth (LC 104)