Depth-First Search
Easy
Return Values in DFS
Understanding how to bubble up information from the bottom of the tree.
5 min
Solve on LeetCodeTop-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?").
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.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.