Find Leaves of Binary Tree

Table of Contents +

This question sounds odd at first. It asks you to peel a tree like an onion. Remove all the leaves. Then remove the new leaves. Keep going until the tree is gone. The real test is spotting that you do not need to remove anything at all. One smart pass does the whole job.

🎯 The Problem

You get a binary tree and must collect its leaves in rounds.

The rules:

  • A binary tree is a structure where each node holds a value and up to two children.
  • A leaf is a node with no children.
  • Each round, collect all the current leaves, then remove them.
  • Removing leaves turns some inner nodes into new leaves. Repeat until the tree is empty.
  • Return the list of rounds.
Input:
        1
       / \
      2   3
     / \
    4   5


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


Explanation:
  Round 1: leaves are 4, 5, 3
  Round 2: after removing them, 2 becomes a leaf
  Round 3: only 1 is left

Here is the tree, with the round number each node is removed in shown next to it.

1 (round 3)

2 (round 2)

3 (round 1)

4 (round 1)

5 (round 1)

🐢 Approach 1: Strip Leaves Again and Again (Brute Force)

The idea in one line: find every leaf, cut it off, then repeat on the smaller tree.

The idea:

  • Match the words of the problem directly.
  • Scan the tree, find every leaf, collect them.
  • Then actually cut them off their parents.

How it works:

  • Scan again. New leaves appeared after the cut.
  • Collect and cut those too.
  • Loop until nothing is left.

Why it is weak:

  • Each round you rescan the whole remaining tree just to find leaves.
  • A tall thin tree needs many rounds, so the time climbs toward O(n²).
  • Cutting nodes off means changing pointers, which is fragile and easy to get wrong.

Here is the repeated-strip code:

find_leaves_repeated_strip.py
def find_leaves(root):
    ans = []
    def strip(node, leaves):
        if not node: return None
        if not node.left and not node.right:
            leaves.append(node.val); return None
        node.left = strip(node.left, leaves)
        node.right = strip(node.right, leaves)
        return node
    while root:
        leaves = []
        root = strip(root, leaves)
        ans.append(leaves)
    return ans

⚡ Approach 2: Group by Height in One Pass (Best)

The idea in one line: the round a node leaves in is exactly its height, so just compute heights once.

The idea:

  • The height of a node is the longest path down to a leaf below it.
  • A leaf has height 0, its parent has height 1, and so on.
  • A node leaves only after all its children are gone, so its round is one more than its tallest child. That is the definition of height.

How it works:

  • Walk bottom-up, children first then the parent. That order is called post-order traversal.
  • For each node, its height is one plus the larger child height.
  • Put the node value into the bucket for its height.

Why it is fast:

  • Height tells you the round directly, with no removing.
  • One pass touches each node once and never edits the tree. That is O(n).
  • When the walk ends, the buckets are the rounds in order.

This diagram shows heights flowing up from the leaves and steering each value into its height bucket.

Leaves: height 0 -> bucket 0

Parent: 1 + max child height

height -> which bucket

bucket[0], bucket[1], ... are the rounds

Steps to Solve

  1. Make a list of buckets, one per height. Start empty and grow as needed.
  2. Walk the tree post-order, children before the parent.
  3. For a missing node, treat its height as -1 so a leaf comes out as 0.
  4. For a real node, its height is one plus the larger of its two child heights.
  5. Add the node value to the bucket for that height.
  6. Return the buckets in order. They are the rounds.

This Python version returns the height from a recursive helper and appends each value to the bucket for its height.

find_leaves.py
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None




def find_leaves(root):
    buckets = []                       # buckets[h] = nodes removed in round h+1


    def height(node):
        if not node:
            return -1                  # a missing node has height -1
        left_h = height(node.left)     # height of left subtree
        right_h = height(node.right)   # height of right subtree
        h = 1 + max(left_h, right_h)   # this node is one above its taller child
        if h == len(buckets):
            buckets.append([])         # grow when a new height appears
        buckets[h].append(node.val)    # drop the value into its height bucket
        return h


    height(root)
    return buckets




root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print(find_leaves(root))

The output of the above code will be:

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

Let us walk the Python version line by line, because the height idea is the whole solution.

The line buckets = [] holds the answer. Position h in this list is the round for nodes of height h. We grow it as new heights appear.

The helper def height(node) returns the height of node and, as a side effect, files the node into its bucket. Returning the height is what lets the parent compute its own height.

The line if not node: return -1 handles a missing child. We pick -1 on purpose. A leaf has no children, so both child calls return -1. Then 1 + max(-1, -1) is 0. So a leaf gets height 0, exactly round one.

The lines left_h = height(node.left) and right_h = height(node.right) recurse into the children first. Children finish before the parent. That children-first order is post-order, and it is what makes height correct.

The line h = 1 + max(left_h, right_h) is the core. A node sits one level above its taller child. That matches the round it leaves in.

The line if h == len(buckets): buckets.append([]) grows the list only when a brand new, taller height shows up. Heights appear in increasing order, so this check is enough.

The line buckets[h].append(node.val) files the value in its round.

Finally height(root) runs the whole walk, and return buckets hands back the rounds in order.

⏱️ Time and Space Complexity

The repeated-stripping way rescans the remaining tree every round, so it can reach O(n²) on a tall tree. The height-grouping way touches each node once and never edits the tree. So it is a clean single pass, O(n). It uses O(n) memory for the buckets, plus the recursion stack.

Approach Time Complexity Space Complexity
Repeatedly strip leaves O(n²) O(n)
Group by height in one pass O(n) O(n)

Tip

The whole problem collapses once you see that a node’s removal round equals its height. Say that out loud in the interview. It proves you found the pattern instead of simulating the steps.

🧩 Key Takeaways

  • ✅ A node leaves in a round equal to its height, where a leaf has height 0.
  • ✅ Height is one plus the taller of the two child heights.
  • ✅ Use a missing-child height of -1 so leaves come out as 0.
  • ✅ Walk post-order, children first, and file each value into its height bucket.
  • ✅ This needs only one pass and never edits the tree, so it runs in O(n).

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What decides the round in which a node is removed?

    Why: A node is removed only after all its children, so its round equals its height. Leaves have height 0.

  2. 2

    What height do we return for a missing (null) node?

    Why: Using -1 for a missing node makes a leaf compute to height 0, which is exactly round one.

  3. 3

    In which order does the optimal solution visit nodes?

    Why: It uses post-order so each child's height is known before the parent computes its own.

  4. 4

    Why is the height-grouping approach faster than repeated stripping?

    Why: One post-order pass handles every node, avoiding the repeated rescans that push stripping toward O(n²).

Score: 0 / 4

🚀 What’s Next?

Previous Range Sum of BST Next Sum Root to Leaf Numbers