LeetCode 366 - Find Leaves of Binary Tree

The problem asks us to repeatedly remove all leaf nodes from a binary tree and record the values removed during each round. A leaf node is a node with no left or right child.

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 366

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to repeatedly remove all leaf nodes from a binary tree and record the values removed during each round.

A leaf node is a node with no left or right child. During each iteration, we collect every current leaf node, remove them conceptually from the tree, and continue the process until the tree becomes empty.

The input is the root node of a binary tree. The output is a list of lists, where each inner list contains the values removed during one round of leaf removal.

For example, consider this tree:

        1
       / \
      2   3
     / \
    4   5

In the first round, nodes 4, 5, and 3 are leaves, so we collect them:

[4,5,3]

After removing them, the tree becomes:

    1
   /
  2

Now 2 is a leaf:

[2]

Finally, 1 becomes the only remaining leaf:

[1]

So the result is:

[[4,5,3],[2],[1]]

The constraints are relatively small, with at most 100 nodes. Even moderately inefficient approaches could pass, but the goal is to design a clean and scalable solution. Since the problem involves repeatedly identifying and removing leaves, we should think carefully about whether we can avoid physically modifying the tree multiple times.

Several edge cases are important:

  • A tree with only one node. That node is immediately a leaf.
  • A completely skewed tree, where each removal round only removes one node.
  • Trees with uneven subtree depths, where leaves appear at different levels.
  • Trees where many leaves exist simultaneously.

The problem guarantees that the input is a valid binary tree and contains at least one node.

Approaches

Brute Force Approach

The most direct solution is to simulate the process exactly as described.

During each round:

  1. Traverse the entire tree.
  2. Identify all current leaves.
  3. Store their values.
  4. Remove them from their parents.
  5. Repeat until the tree is empty.

This approach is correct because it follows the problem statement literally. Every iteration removes exactly the nodes that are currently leaves.

However, this method is inefficient because the tree may be traversed many times. In the worst case, such as a completely skewed tree, only one node is removed per round. If there are n nodes, we may perform n full traversals, leading to quadratic time complexity.

Optimal Approach

The key insight is that we do not actually need to remove nodes physically.

Instead, we can observe that the round in which a node gets removed depends entirely on the height of that node from the bottom of the tree.

  • Leaf nodes are removed first, so they belong to level 0.
  • Their parents become leaves after that, so they belong to level 1.
  • Higher ancestors belong to progressively larger levels.

This means the problem can be transformed into:

Group nodes by their height from the bottom.

We can compute this height using a postorder depth first search.

For each node:

  • Compute the height of the left subtree.
  • Compute the height of the right subtree.
  • The node's height is:
max(leftHeight, rightHeight) + 1

Nodes with the same height are removed during the same round.

This avoids repeated traversals and computes everything in one DFS pass.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly traverses and modifies the tree
Optimal O(n) O(n) Single DFS groups nodes by removal round

Algorithm Walkthrough

Optimal DFS Height-Based Algorithm

  1. Start a postorder DFS traversal from the root.

Postorder traversal is important because we must process children before processing the current node. A node's removal round depends on when its children disappear. 2. Define the height of a null node as -1.

This simplifies the leaf calculation naturally. If both children are null:

height = max(-1, -1) + 1 = 0

So leaf nodes automatically get height 0. 3. Recursively compute the height of the left subtree.

This tells us how many rounds are needed before the left subtree disappears completely. 4. Recursively compute the height of the right subtree.

Similarly, this determines how long the right subtree survives. 5. Compute the current node's height.

currentHeight = max(leftHeight, rightHeight) + 1

The node can only become a leaf after both subtrees are gone, so it depends on the deeper subtree. 6. Use the height as an index into the result array.

If this height has not appeared before, create a new inner list.

Then append the current node's value to:

result[currentHeight]
  1. Return the computed height to the parent call.

This allows ancestor nodes to determine their own removal rounds. 8. After DFS completes, return the result.

Each index in the result corresponds to one round of leaf removal.

Why it works

The algorithm works because a node becomes a leaf exactly after all nodes beneath it have already been removed. Therefore, the removal round of a node is equal to its height measured from the bottom of the tree. Postorder traversal guarantees that children's heights are computed before the parent's height, so every node is placed into the correct removal group.

Python 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

from typing import List, Optional

class Solution:
    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []

        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return -1

            left_height = dfs(node.left)
            right_height = dfs(node.right)

            current_height = max(left_height, right_height) + 1

            if current_height == len(result):
                result.append([])

            result[current_height].append(node.val)

            return current_height

        dfs(root)
        return result

The solution uses a nested DFS helper function that returns the height of each node measured from the bottom of the tree.

The base case returns -1 for null nodes. This allows leaf nodes to naturally compute to height 0.

The recursion processes the left and right subtrees first. This is postorder traversal, which is necessary because a node's removal round depends on its children.

After computing the heights of both subtrees, the current node's height is determined using:

max(left_height, right_height) + 1

The result list is dynamically expanded whenever a new height level appears. Each node value is appended into the list corresponding to its removal round.

Finally, the DFS begins at the root, and the fully constructed result is returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findLeaves(root *TreeNode) [][]int {
    result := [][]int{}

    var dfs func(node *TreeNode) int

    dfs = func(node *TreeNode) int {
        if node == nil {
            return -1
        }

        leftHeight := dfs(node.Left)
        rightHeight := dfs(node.Right)

        currentHeight := max(leftHeight, rightHeight) + 1

        if currentHeight == len(result) {
            result = append(result, []int{})
        }

        result[currentHeight] = append(result[currentHeight], node.Val)

        return currentHeight
    }

    dfs(root)

    return result
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation follows the same logic as the Python version. The main difference is that Go requires explicit slice management and helper functions.

The result is represented as a slice of integer slices:

[][]int

The DFS helper is implemented as a recursive closure. Since Go does not provide a built-in max function for integers, a small helper function is included.

Nil pointers are handled directly using:

if node == nil

This corresponds to the Python check for None.

Worked Examples

Example 1

Input:

root = [1,2,3,4,5]

Tree:

        1
       / \
      2   3
     / \
    4   5

DFS Traversal State

Node Left Height Right Height Current Height Result After Processing
4 -1 -1 0 [[4]]
5 -1 -1 0 [[4,5]]
2 0 0 1 [[4,5],[2]]
3 -1 -1 0 [[4,5,3],[2]]
1 1 0 2 [[4,5,3],[2],[1]]

Final output:

[[4,5,3],[2],[1]]

Example 2

Input:

root = [1]

Tree:

1

DFS Traversal State

Node Left Height Right Height Current Height Result After Processing
1 -1 -1 0 [[1]]

Final output:

[[1]]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(n) Result storage plus recursion stack

The DFS traverses each node exactly one time, and each visit performs only constant work. Therefore, the total running time is linear in the number of nodes.

The space complexity comes from two sources:

  • The recursion stack, which can reach O(h) where h is the tree height.
  • The result structure, which stores all node values.

In the worst case of a skewed tree, recursion depth becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findLeaves(self, root):
        result = []

        def dfs(node):
            if not node:
                return -1

            left_height = dfs(node.left)
            right_height = dfs(node.right)

            current_height = max(left_height, right_height) + 1

            if current_height == len(result):
                result.append([])

            result[current_height].append(node.val)

            return current_height

        dfs(root)
        return result

sol = Solution()

# Example 1
root1 = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3)
)
assert sol.findLeaves(root1) == [[4, 5, 3], [2], [1]]  # standard example

# Example 2
root2 = TreeNode(1)
assert sol.findLeaves(root2) == [[1]]  # single node tree

# Left skewed tree
root3 = TreeNode(1, TreeNode(2, TreeNode(3)))
assert sol.findLeaves(root3) == [[3], [2], [1]]  # one node removed per round

# Right skewed tree
root4 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
assert sol.findLeaves(root4) == [[3], [2], [1]]  # asymmetric structure

# Complete binary tree
root5 = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7))
)
assert sol.findLeaves(root5) == [[4, 5, 6, 7], [2, 3], [1]]  # balanced tree

# Tree with negative values
root6 = TreeNode(
    -1,
    TreeNode(-2),
    TreeNode(-3)
)
assert sol.findLeaves(root6) == [[-2, -3], [-1]]  # negative node values

# Uneven depth tree
root7 = TreeNode(
    1,
    TreeNode(2, TreeNode(4)),
    TreeNode(3)
)
assert sol.findLeaves(root7) == [[4, 3], [2], [1]]  # mixed subtree depths
Test Why
[1,2,3,4,5] Validates the main example
[1] Tests smallest possible tree
Left skewed tree Tests worst-case recursion depth
Right skewed tree Tests asymmetric structure handling
Complete binary tree Tests many simultaneous leaves
Negative values Confirms value sign does not matter
Uneven depth tree Verifies height grouping correctness

Edge Cases

A single-node tree is the smallest valid input and can easily expose off-by-one errors in height calculations. If the base case is implemented incorrectly, the root might be placed into the wrong group. This implementation handles it correctly because null children return -1, causing the single node to compute to height 0.

A completely skewed tree behaves similarly to a linked list. In this situation, only one node is removed during each round. Naive implementations may repeatedly traverse the entire tree, leading to quadratic performance. The DFS height-based solution still processes each node exactly once, so the runtime remains linear.

Trees with uneven subtree depths are another common source of bugs. A node should only become removable after both subtrees disappear. The algorithm handles this correctly by using:

max(leftHeight, rightHeight) + 1

This guarantees that the node waits for the deeper subtree before determining its removal round.

Another subtle edge case occurs when multiple leaves exist simultaneously at different positions in the tree. The implementation correctly groups all nodes with the same height together, regardless of traversal order, which matches the problem statement where ordering inside each round does not matter.