Tree DFS
One recursive function, and a contract you can say out loud: this is what the call returns to its parent, and this is what it records on the side. Almost every binary-tree question is a choice of those two.
Problems worked on this page, and more to practise
- 543. Diameter of Binary Tree
- 236. Lowest Common Ancestor of a Binary Tree
- 124. Binary Tree Maximum Path Sum
- 104. Maximum Depth of Binary Tree
- 226. Invert Binary Tree
- 101. Symmetric Tree
- 112. Path Sum
- 110. Balanced Binary Tree
- 98. Validate Binary Search Tree
- 1448. Count Good Nodes in Binary Tree
- 337. House Robber III
- 437. Path Sum III
- 297. Serialize and Deserialize Binary Tree
What is the difference between what a tree recursion returns and what it records?
The return value is the one thing a parent needs in order to extend the answer through itself, and it is usually a property of the subtree such as its height or its best downward sum. What you record is the answer you are actually being asked for, kept in a variable outside the recursion because no ancestor can use it. In Diameter of Binary Tree the call returns the height and records the diameter. Conflating the two is the single most common reason a tree solution is wrong.
Why are these problems solved in post-order rather than pre-order?
Post-order means a node does its own work only after both children have returned. You need that whenever a node’s answer is built out of its children’s answers, which is the case for height, diameter, balance, subtree sums, and best path. Pre-order is the right order when information flows the other way, from the root down: validating a BST carries an allowed range down, and Path Sum carries the remaining target down.
How much memory does tree DFS use?
One stack frame per node on the path from the root to where you are now, so O(h) where h is the height. On a balanced tree that is about log n. On a tree shaped like a linked list it is n, and CPython stops at a recursion depth near 1000, so a skewed tree of 100,000 nodes raises RecursionError. The fix is an explicit stack with a visited flag, which turns the same post-order into a loop.
Why does the base case return 0 and not something else?
It returns the value that leaves the combine step unchanged, the identity. For height the combine is 1 + max(left, right), so an empty subtree is 0 tall. For a sum of node values it is also 0, because adding nothing changes nothing. For Lowest Common Ancestor the call returns a node, so the base case returns None, meaning “nothing found down here”. Pick that value correctly and every leaf works with no special case at all.
When should I use BFS on a tree instead of DFS?
When the question is about levels or about the nearest something. Right side view, level order, and minimum depth are all level questions, and a level question wants a queue. Minimum Depth is the trap: the obvious DFS recursion 1 + min(left, right) is wrong at any node with exactly one child, because the missing side returns 0 and the node claims a leaf that is not there. DFS can be fixed, but it still visits every node, while BFS stops at the first leaf it meets.