LeetCode 366: Find Leaves of Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 366: Find Leaves of Binary Tree?

LeetCode 366: Find Leaves of Binary Tree gives you a binary tree, and your task is to collect all leaf nodes in the order they’d be removed if you repeatedly stripped off the outermost leaves until the tree is empty. Each removal forms a group, and you return these groups as a list of lists. It’s a tree problem with a twist on level-order processing!

Problem Statement

• Input:
• root: Root node of a binary tree (TreeNode class).
• Output: List[List[int]] - List of lists, where each sublist contains the values of leaves removed in one pass.
• Rules:
• A leaf is a node with no children.
• Remove all leaves in each pass until the tree is empty.
• Order within each sublist doesn’t matter.

Constraints

• Number of nodes: 1 to 10³.
• Node values: -100 to 100.
• Tree is a valid binary tree.

Examples

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

Copy code```
  1
 / \
2   3

/ \ 4 5 ```

• Output: [[4,5,3],[2],[1]]
• Pass 1: Remove leaves 4,5,3 → [4,5,3].
• Pass 2: Remove leaf 2 → [2].
• Pass 3: Remove root 1 → [1].

• Tree:

1 / 2 / 3

• Output: [[3],[2],[1]]
• Pass 1: Remove leaf 3 → [3].
• Pass 2: Remove leaf 2 → [2].
• Pass 3: Remove root 1 → [1].

These show the leaf-stripping process—let’s solve it!

Understanding the Problem: Collecting Leaves Layer by Layer

To tackle LeetCode 366 in Python, we need to: 1. Identify leaves (nodes with no children). 2. Group them by removal pass, from outermost to root. 3. Return the groups in order of removal.

A naive approach might repeatedly scan the tree, but we can optimize. We’ll use:

• Best Solution: Bottom-up DFS with height tracking—O(n) time, O(n) space—fast and elegant.
• Alternative Solution: Top-down DFS with repeated removal—O(n²) time, O(n) space—intuitive but slower.

Let’s gather with the best solution!

Best Solution: Bottom-Up DFS with Height Tracking

Why This Is the Best Solution

The bottom-up DFS approach runs in O(n) time by computing each node’s height (distance to its deepest leaf) in a single pass, using this to group nodes by their removal order. It’s the most efficient—leveraging tree structure without repeated traversals!

How It Works

Think of it like measuring leaf distance:

• DFS: Traverse bottom-up, calculating height as max(left, right) + 1.
• Height as Index: Height indicates removal pass (leaves at height 0, parents at 1, etc.).
• Group: Store node values in a list indexed by height.
• Result: Convert to list of lists.

It’s like peeling the tree from the bottom up!

Step-by-Step Example

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

• Tree:

1 / \ 2 3 / \ 4 5

• DFS:
• 4: Height=0 (leaf) → [(4,0)].
• 5: Height=0 (leaf) → [(5,0)].
• 2: Height=max(0,0)+1=1 → [(2,1)].
• 3: Height=0 (leaf) → [(3,0)].
• 1: Height=max(1,0)+1=2 → [(1,2)].
• Group by Height:
• 0: [4,5,3].
• 1: [2].
• 2: [1].
• Result: [[4,5,3], [2], [1]].

For root = [1,2,null,3]:

• DFS:
• 3: Height=0 → [(3,0)].
• 2: Height=1 → [(2,1)].
• 1: Height=2 → [(1,2)].
• Group: [[3], [2], [1]].

Code with Explanation

Here’s the Python code using bottom-up DFS:

Copy codeclass Solution:
    def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        # Dictionary to store nodes by height
        height_map = defaultdict(list)

        # DFS to compute height and group nodes
        def get_height(node):
            if not node:
                return -1  # Base case: null node has height -1
            # Height is max of left and right subtrees plus 1
            left_height = get_height(node.left)
            right_height = get_height(node.right)
            curr_height = max(left_height, right_height) + 1
            # Group node value by its height
            height_map[curr_height].append(node.val)
            return curr_height

        # Run DFS and build result
        get_height(root)
        # Convert height_map to list of lists (sorted by height)
        return [height_map[i] for i in range(len(height_map))]

Explanation

• Line 4: height_map: Defaultdict to group node values by height (removal pass).
• Lines 6-15: get_height:
• Base case: Return -1 for null nodes (leaves have height 0).
• Recursively compute left and right heights.
• Current height = max(left, right) + 1.
• Append node value to height_map[curr_height].
• Return height for parent.
• Line 18: Run DFS starting at root.
• Line 20: Convert height_map to list, keys (heights) are naturally 0 to max_depth.

• Time Complexity: O(n)—single DFS pass over all nodes.
• Space Complexity: O(n)—height_map stores all node values, plus recursion stack.

This is like a tree leaf harvest—gather by height in one sweep!

Alternative Solution: Top-Down DFS with Repeated Removal

Why an Alternative Approach?

The top-down DFS with repeated removal runs in O(n²) time by simulating the leaf-stripping process, repeatedly finding and removing leaves. It’s less efficient but mirrors the problem’s intuitive process—great for visualization!

How It Works

• DFS: Find leaves in each pass, collect them, mark as removed.
• Repeat: Continue until tree is empty.
• Result: List of leaf groups per pass.

Step-by-Step Example

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

• Pass 1:
• Leaves: 4,5,3.
• Remove: 2→[4,null], 3→null, Result: [[4,5,3]].
• Pass 2:
• Leaves: 2.
• Remove: 1→[2,null], Result: [[4,5,3], [2]].
• Pass 3:
• Leaf: 1.
• Remove: Root=null, Result: [[4,5,3], [2], [1]].

Code with Explanation

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

        # Helper to find and remove leaves
        def remove_leaves(node, parent=None, is_left=True):
            if not node:
                return False
            # Leaf if no children
            if not node.left and not node.right:
                result[-1].append(node.val)
                if parent:
                    if is_left:
                        parent.left = None
                    else:
                        parent.right = None
                return True
            # Recurse on children
            remove_leaves(node.left, node, True)
            remove_leaves(node.right, node, False)
            return False

        # Repeat until tree is empty
        while root:
            result.append([])  # New pass
            if remove_leaves(root):
                root = None  # Root was a leaf
        return result

Explanation

• Line 4: result: List to store leaf groups.
• Lines 6-20: remove_leaves:
• Base case: Null node, return False.
• If leaf: Append value to current pass, remove from parent, return True.
• Recurse on children, track parent and side (left/right).
• Lines 22-26: Main loop:
• Start new pass, call remove_leaves.
• If root is removed (True), set root to None.
• Time: O(n²)—each pass O(n), up to n passes for skewed tree.
• Space: O(n)—recursion stack and result.

It’s like pruning the tree pass by pass!

Comparing the Two Solutions

• Bottom-Up DFS (Best):
• Time: O(n)—single pass.
• Space: O(n)—height_map.
• Pros: Fast, efficient.
• Cons: Less intuitive process.
• Top-Down DFS (Alternative):
• Time: O(n²)—repeated passes.
• Space: O(n)—stack and result.
• Pros: Mirrors removal process.
• Cons: Slower for deep trees.

Bottom-up wins for speed!

Additional Examples and Edge Cases

• [1]: [[1]].
• [1,null,2]: [[2], [1]].
• Deep tree: Bottom-up scales better.

Both handle these, bottom-up is faster.

Complexity Breakdown

• Bottom-Up:
• Time: O(n).
• Space: O(n).
• Top-Down:
• Time: O(n²).
• Space: O(n).

Bottom-up excels for efficiency.

Key Takeaways

• Bottom-Up: Height-based grouping—fast and smart!
• Top-Down: Simulate removal—clear and visual!
• Trees: Depth drives solutions.
• Python Tip: DFS rocks—see [Python Basics](/python/basics).

Final Thoughts: Gather Those Leaves

LeetCode 366: Find Leaves of Binary Tree in Python is a tree-layering challenge. Bottom-up DFS is the efficiency champ, while top-down builds intuition. Want more? Try LeetCode 104: Maximum Depth or LeetCode 637: Average of Levels. Ready to prune? Visit Solve LeetCode 366 on LeetCode (premium) and collect those leaves today!