Passing Values Down and Up
MediumContext descends, results ascend
Problem
Pass context down (like a running path or depth) and results up in a single DFS.
Carry information down as you go and hand answers back as you return.
The idea
Information can flow both ways in one traversal: parameters carry context downward, such as the running path or the allowed value range, while the return value carries results upward. Recognising which direction a given fact needs to travel is most of the design.
The trick
- Downward: depth, running sum, valid range, the path so far.
- Upward: heights, counts, subtree sums, booleans.
- Some problems need both at once — validate-BST is the classic example.
Step 1 of 8. A node's height is 1 + the taller of its two subtrees. Solve leaves first, then bubble up.
1/8
Optimal
timeO(n)spaceO(h)
Post-order combine.
1function depth(node) {2 if (!node) return 0;3 return 1 + Math.max(depth(node.left), depth(node.right));4}Input
- nodes
- 6, 5 edges
Output
- max depth
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- path sum check
- Output:
- true/false
Finished the walkthrough? Add it to your streak.