Find Leaves of Binary Tree
Problem
Given the root of a binary tree, return a list of lists where each sublist contains the values of the nodes that are removed as leaves in each iteration until the tree is empty.
- The number of nodes in the tree is in the range [1, 1000]
- −1000 ≤ Node.val ≤ 1000
Example
root = [1,2,3,4,5][[4,5,3],[2],[1]]The algorithm works by assigning a height to each node, defined as the number of edges on the longest path from the node down to a leaf. Leaves have height 0. For the example tree: 1. Nodes 4, 5, and 3 are leaves with height 0, so they form the first list. 2. Node 2 has children 4 and 5, so its height is 1, forming the second list. 3. Node 1 has children 2 and 3, so its height is 2, forming the last list. This height-based grouping corresponds exactly to the order in which nodes would be removed if leaves were iteratively pruned.
Approach
Straightforward Solution
A naive approach would simulate the iterative removal of leaves by repeatedly traversing the tree to find leaves and remove them, which is inefficient and can lead to O(n²) time complexity.
Core Observation
The height of a node in a binary tree can be defined recursively as 1 plus the maximum height of its children, with leaves having height 0. Grouping nodes by their height naturally partitions them into layers corresponding to the order in which they would be removed as leaves.
Path to Optimal
PreviewInstead of simulating leaf removal, the problem can be reframed as computing the height of each node via a post-order DFS traversal. This approach assigns each node a height that corresponds to the iteration it would be removed…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewPerform a DFS that returns the height of each node. For each node, compute the height of its left and right children, take the maximum, add one, and append the node's value to the list corresponding to that height…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is visited exactly once during the DFS traversal, and all operations per node are O(1), resulting in linear time relative to the number of nodes.
Space
O(n)
The recursion stack can grow up to O(h) where h is the height of the tree, which is O(n) in the worst case. Additionally, the output list stores all node values, which is O(n) space.
Pattern Spotlight
DFS (Post-Order Traversal with State Aggregation)
When a problem requires grouping nodes by a property dependent on their descendants, a post-order DFS that computes and returns that property bottom-up enables efficient aggregation without explicit simulation.
Solution
| 1 | class Solution: |
| 2 | def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]: |
| 3 | res = [] |
| 4 | |
| 5 | def dfs(node): |
| 6 | if not node: |
| 7 | return -1 |
| 8 | |
| 9 | left = dfs(node.left) |
| 10 | right = dfs(node.right) |
| 11 | |
| 12 | height = 1 + max(left, right) |
| 13 | |
| 14 | if height == len(res): |
| 15 | res.append([]) |
| 16 | |
| 17 | res[height].append(node.val) |
| 18 | |
| 19 | return height |
| 20 | |
| 21 | dfs(root) |
| 22 | return res |
Step-by-Step Solution
Compute Node Heights via Post-Order DFS and Group Nodes
| 3 | res = [] |
| 5 | def dfs(node): |
| 6 | if not node: |
| 7 | return -1 |
| 9 | left = dfs(node.left) |
| 10 | right = dfs(node.right) |
| 12 | height = 1 + max(left, right) |
| 14 | if height == len(res): |
| 15 | res.append([]) |
| 17 | res[height].append(node.val) |
| 19 | return height |
| 21 | dfs(root) |
| 22 | return res |
Objective
To recursively compute the height of each node and group nodes by their height in the result list.
Key Insight
By performing a post-order DFS, the algorithm ensures that the heights of the children are computed before the parent. The height of a node is 1 plus the maximum height of its children, which naturally corresponds to the iteration at which the node would be removed as a leaf. Grouping nodes by height during traversal avoids simulating leaf removal and achieves the solution in a single pass.
Interview Quick-Check
Core Logic
The DFS returns the height of each node, defined as 1 + max(left child's height, right child's height), enabling grouping nodes by their removal iteration.
State & Boundaries
The base case returns -1 for null nodes, so leaves have height 0, ensuring correct height calculation.
Common Pitfalls & Bugs
Forgetting to append a new list when the current height equals the length of the result list leads to index errors or missing groups.
Complexity
This approach visits each node once, resulting in O(n) time and O(n) space complexity.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
res = []Initialize the result list to store groups of leaves by height.
This list accumulates nodes grouped by their computed height, which corresponds to the iteration they would be removed as leaves.
def dfs(node):Define the DFS helper function to compute node heights.
Encapsulating the height computation in a recursive function enables a clean post-order traversal that aggregates state bottom-up.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does grouping nodes by their height computed via DFS correspond to the order in which leaves are removed iteratively?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Find Leaves of Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find Leaves of Binary Tree drill