Domain 2MediumCORE

Find Leaves of Binary Tree

We are given the root of a binary tree and asked to simulate an iterative process where we repeatedly strip off all current leaf nodes. Each iteration produces one list in our output, representing the values collected at that specific 'layer' before removal. The goal is to return these layers as a 2D array (list of lists).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree#Depth-first Search

366. Find Leaves of Binary Tree

Model: qwen3.5:9b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 72.1%


Problem Breakdown

We are given the root of a binary tree and asked to simulate an iterative process where we repeatedly strip off all current leaf nodes. Each iteration produces one list in our output, representing the values collected at that specific “layer” before removal. The goal is to return these layers as a 2D array (list of lists).

Inputs:

  • root: A pointer to the root node of a binary tree (TreeNode).

Outputs:

  • A list of lists where each inner list contains values from one iteration’s leaf collection.

Constraints & Edge Cases:

  • Node count: [1, 100]. This is small enough that O(N^2) might pass, but we should aim for optimal.
  • Values: 1 <= val <= 100 (no negative values to worry about).
  • Tree structure can be skewed or balanced.
  • Single node tree must return one list with the single value.

Intuition

If I were to literally simulate this process by physically removing nodes from a data structure, every iteration would require traversing the entire remaining tree to find new leaves and rebuild links. That simulation approach is O(N^2) in time complexity because we touch each node multiple times across iterations (once per layer it belongs to).

Instead of modifying the tree structure repeatedly, I should look for an invariant property that determines when a specific node gets removed. A leaf has no children. Its “height” relative to itself is 0. If a parent has one child which is a leaf, once that leaf goes away (conceptually), the parent becomes a new leaf. This suggests we can calculate how many layers of leaves sit above any given node before it gets exposed as a leaf. This metric corresponds exactly to the height of the subtree rooted at each node (where an empty tree has height -1 or 0 depending on convention). If I define dfs returning the max depth from this node down to its nearest null child, that return value tells me precisely which index in my result list this node belongs to.

Approach

I will use a Depth-First Search (DFS) with post-order traversal logic because we need information about children before processing the parent’s height.

  1. Initialize an empty res list of lists. This acts as our dynamic array where indices represent “heights” or layers.
  2. Define a recursive helper function that takes a node and returns its calculated depth/height relative to leaves.
  3. Base Case: If the current node is null, return -1 (or handle appropriately so parents calculate correctly). I’ll use -1 for None children so that a leaf’s height calculation becomes max(-1, -1) + 1 = 0.
  4. Recursive Step: Recursively call on left and right children to get their heights (left_h, right_h).
  5. The current node’s height is h = max(left_h, right_h) + 1. This tells us exactly which layer this node belongs in the output (index h of our result list).
  6. Dynamic Resizing: If index h doesn’t exist yet in res, append an empty list to ensure we can store values there. Then add current node’s value to res[h].
  7. Return h up the recursion stack so parents know how deep their subtree is.

Complexity Analysis

  • Time: O(N), where N is the number of nodes. We visit every node exactly once in a single DFS traversal. The operations inside each call are constant time (excluding list appends which amortize to O(1)).
  • Space: O(H) for recursion stack space, where H is the height of the tree. In worst case (skewed tree), this degrades to O(N). We also use O(N) extra space for the output storage itself.

Solution

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findLeaves(root):
    res = []  # Stores the layers of leaves
    
    def dfs(node):
        if not node: 
            return -1
        
        l_h = dfs(node.left)
        r_h = dfs(node.right)
        
        h = max(l_h, r_h) + 1
        
        while len(res) <= h:
            res.append([])
            
        res[h].append(node.val)
        
        return h
    
    if not root: 
        return [] # Though constraints say nodes >= 1
        
    dfs(root)
    
    return res

# Example usage logic (not part of function signature):
# Input: [1,2,3,4,5] -> Output: [[4,5,3],[2],[1]] or similar orderings per layer

Edge Cases Handled

  • Single Node Tree: The root has no children. dfs returns 0 for height. res[0] gets the value. Returns [ [val] ]. Correct.
  • Skewed Trees (Left/Right only): Recursion depth increases linearly, but logic holds because max child height propagates correctly up to the root which ends up at index N-1 or similar depending on structure.
  • Null Children: Handled by returning -1 from dfs(None). This ensures a leaf node calculates its own height as 0 (max(-1, -1) + 1).