Trees · Stage 2 of 3
Bottom-Up Recursion
Return one answer from each subtree and combine them at the parent
Foundations
In the first lesson, each call did its work on the tree and returned the node. Now, what if each call returns a number instead, a fact about its subtree, and the parent builds its own answer from its children's?
Bottom-up recursion defines a node's answer from the answers of its subtrees, plus a base case for None. A call asks both children, waits, combines their results with its own value, and returns one number to its parent. No call needs to know the path above it, so nothing is copied on the way down.
On the tree read from nums = [7, 1, 5, 3, 6], count the nodes bottom-up: None returns 0, each leaf returns 1 + 0 + 0 = 1, node 1 returns 1 + 1 + 1 = 3, node 5 returns 1, and the root returns 1 + 3 + 1 = 5. Each node answered once, from the two numbers its children handed up.
Case Scenario
The problem
Maximum Depth of Binary Tree
Return the maximum depth of the binary tree. An empty tree has depth 0.
- Input
- root = [3, 9, 20, None, None, 15, 7]
- Output
- 3
Maximum Depth of Binary Tree asks for the number of nodes on the longest path from the root down to a leaf. Bottom-up, a None child has depth 0, and every node's depth is 1 + max(left, right). For root = [3, 9, 20, None, None, 15, 7], leaves 9, 15, and 7 return 1, node 20 returns 2, and the root returns 3.
The direct approach carries the path down: walk every path from the root to a leaf, copying the list of values at each node, and keep the longest. It works, but each node copies a list as long as its depth, O(n · h) time, and a deep path holds O(h²) copied values, all to compute one number per node.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.