Return Values in DFS
Understanding how to bubble up information from the bottom of the tree.
Top-Down vs Bottom-Up
There are two main ways to solve Tree problems:
- Top-Down (Pre-order): Pass values down to children. (e.g., "Current path sum is 10, child add your value to 10").
- Bottom-Up (Post-order): Ask children for information and aggregate it. (e.g., "Left child, what is your height? Right child, what is yours?").
Interactive Visualization
Compute one tree’s height both ways. Bottom-up, a node’s number appears when it returns, so the numbers fill in from the leaves. Top-down, a node’s number is the depth it was handed, so they fill in from the root, and the answer is collected in best.
Bubbling Up Values
Most "Find height", "Find diameter", or "Check balance" problems use Bottom-Up.
Logic flow:
- Go down to
null(Base case returns 0 or expected null value). - As functions return, they pass data back to their parent.
- The parent calculates its own result based on left/right return values and returns that to its own parent.
Example: Logic for Height
Height = max(LeftHeight, RightHeight) + 1
This single line captures the essence of Bottom-Up DFS. You cannot know your height until your children tell you theirs.
Both Directions
The height of a tree computed bottom-up from return values, and top-down by passing depth down, in every language.
Return Values in DFS Code
1function bottomUp(node) {2 if (!node) return 0;3 const left = bottomUp(node.left);4 const right = bottomUp(node.right);5 return Math.max(left, right) + 1;6}78function topDown(root) {9 let best = 0;1011 function dfs(node, depth) {12 if (!node) return;13 best = Math.max(best, depth);14 dfs(node.left, depth + 1);15 dfs(node.right, depth + 1);16 }1718 dfs(root, 1);19 return best;20}