Skip to main content

366 - Find Leaves of Binary Tree

Difficulty: Medium | Pattern: DFS (Height-based grouping) | Company tags: LinkedIn, Amazon, Google

Problem Statement​

Given the root of a binary tree, collect the tree's nodes as if you were doing this:

  • Collect all the leaf nodes.
  • Remove all the leaf nodes.
  • Repeat until the tree is empty.

Return the resulting 2D list.

Example:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]

Approach: DFS with Height-based Grouping — O(n), O(n)​

Key insight: A node's "height" in this problem is 0 for leaves, 1 for nodes whose children are leaves, etc. This height equals which collection layer the node belongs to. Compute heights via post-order DFS.

Algorithm Flow​

def findLeaves(root) -> list[list[int]]:
    result = []
    
    def dfs(node) -> int:
        if not node:
            return -1
        
        height = 1 + max(dfs(node.left), dfs(node.right))
        
        while len(result) <= height:
            result.append([])
        result[height].append(node.val)
        
        return height
    
    dfs(root)
    return result

Dry Run​

Tree: 1(root), left=2(left=4,right=5), right=3

Post-order:

  • dfs(4): height = 1+max(-1,-1) = 0 → result[0]=[4]
  • dfs(5): height = 0 → result[0]=[4,5]
  • dfs(2): height = 1+max(0,0) = 1 → result[1]=[2]
  • dfs(3): height = 0 → result[0]=[4,5,3]
  • dfs(1): height = 1+max(1,0) = 2 → result[2]=[1]

Result: [[4,5,3],[2],[1]] ✓

Why Height-Based?​

This is equivalent to repeatedly removing leaves. A node is removed in round k iff it's at height k — all its descendants have already been removed in earlier rounds.

Complexity​

  • Time: O(n) — visit each node once
  • Space: O(n)

Key Terms​

TermDefinition
Post-order DFSTraversal that processes both children before the current node — needed here since a node's height depends on its children.
Node heightLongest path from a node down to a leaf; leaves have height 0.
Height-based groupingBucketing nodes by height so that each bucket corresponds to one "leaf removal round".
Removal roundOne pass of removing all current leaves; equivalent to processing all nodes of a given height together.

FAQ​

Q: Why does height directly map to the removal round? A: A node can only be "removed" after all its descendants are removed. Since height is defined recursively as 1 + max(child heights), a node's height equals the number of rounds needed to strip away everything below it — exactly its removal round index.

Q: Why use post-order instead of pre-order or level-order? A: We need each child's height before computing the parent's height, so children must be visited first — that is the definition of post-order.

Q: What happens with a single-node tree? A: dfs(root) returns height 0 immediately (both children are null, so max(-1,-1)+1 = 0), giving result = [[root.val]].

Q: Can this be done iteratively instead of recursively? A: Yes, using an explicit stack with a "visited" marker per node (standard iterative post-order), though the recursive version is far simpler and the tree depth bound makes recursion safe for typical constraints.

Q: How would you solve this if the tree were very unbalanced (e.g., a linked-list-like skewed tree)? A: The approach still works in O(n) time, but recursion depth becomes O(n), risking a stack overflow for very deep trees — an iterative post-order traversal would be safer in that case.

Quick Revision​

  • Goal: repeatedly strip leaves and collect them into layers.
  • Key idea: a node's height (0 for leaves) equals its removal layer index.
  • Use post-order DFS: compute left and right child heights first.
  • height = 1 + max(dfs(left), dfs(right)), with null returning -1.
  • Grow the result list on demand so result[height] exists.
  • Append the node's value to result[height].
  • Return height so the parent can compute its own height.
  • Time: O(n), Space: O(n) for recursion stack and output.
  • Works because descendants always finish processing (and land in earlier layers) before their ancestors.
  • 113 - Path Sum II — another DFS problem that builds path/level-based result lists.
  • 637 - Average of Levels in Binary Tree — similar theme of grouping nodes by a structural depth/height metric.
  • Also related in pattern: any "group nodes by height/depth" tree DFS problem, such as level-order variants using BFS instead of post-order height computation.