Find Leaves of Binary Tree

Medium Trees & BST Postorder + Multiple Return Values Original on LeetCode

Reported atLinkedInOracle

Find Leaves of Binary Tree is a medium trees & bst problem solved with the postorder + multiple return values pattern. The best approach, optimal (group by height in one postorder pass), runs in O(n) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (strip leaves round by round) up.

Problem

You are given the root of a binary tree. Repeat the following until the tree is empty:

  • Collect the values of all current leaves (nodes with no children), from left to right.
  • Remove those leaves from the tree.

Return the collected groups in the order they were removed, as a list of lists.

Examples

Example 1

Input
root = [8, 3, 5, 1, 4]
Output
[[1, 4, 5], [3], [8]]
Why
First 1, 4 and 5 are leaves. Removing them makes 3 a leaf, and finally only 8 is left.

Example 2

Input
root = [6, null, 2, 9]
Output
[[9], [2], [6]]
Why
The tree is a chain 6 -> 2 -> 9, so one node falls off per round.

Example 3

Input
root = [7]
Output
[[7]]
Why
A lone root is already a leaf.

Constraints

  • The tree has 1 to 100 nodes.
  • -100 <= Node.val <= 100

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (strip leaves round by round)O(n · h)O(h)
Optimal (group by height in one postorder pass)O(n)O(h)

1Brute force (strip leaves round by round)

TimeO(n · h)There are h + 1 rounds (h = tree height) and each round walks the remaining tree, up to n nodes.
SpaceO(h)The recursion stack, not counting the output.

Repeat a DFS that detaches every current leaf and records its value, until the root itself has been removed. Visiting left before right keeps each round's leaves in left-to-right order.

  1. While root is not null: start an empty round list.
  2. strip(node): if node is a leaf, record it and return null; else node.left = strip(node.left), node.right = strip(node.right), return node.
  3. root = strip(root); add the round list to the answer.
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        while (root != null) {
            List<Integer> round = new ArrayList<>();
            root = strip(root, round);
            res.add(round);
        }
        return res;
    }

    private TreeNode strip(TreeNode node, List<Integer> round) {
        if (node == null) return null;
        if (node.left == null && node.right == null) {
            round.add(node.val);
            return null;
        }
        node.left = strip(node.left, round);
        node.right = strip(node.right, round);
        return node;
    }
}

2Optimal (group by height in one postorder pass)

TimeO(n)Each node is visited exactly once.
SpaceO(h)The recursion stack goes as deep as the tree, not counting the output.

A node is removed in round height(node), where a leaf has height 0 and any other node has 1 + the larger child height. Compute heights bottom-up and drop each value into the list for its height. Postorder visits same-height nodes from left to right, matching the round order.

  1. height(null) = -1.
  2. h = 1 + max(height(left), height(right)).
  3. If res has only h lists, append a new one; then res[h].add(node.val).
  4. Return h; the answer is res after calling height(root).
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        height(root, res);
        return res;
    }

    private int height(TreeNode node, List<List<Integer>> res) {
        if (node == null) return -1;
        int h = 1 + Math.max(height(node.left, res), height(node.right, res));
        if (res.size() == h) res.add(new ArrayList<>());
        res.get(h).add(node.val);
        return h;
    }
}

Edge cases to test

  • A single node
  • A chain (every round removes exactly one node)
  • A perfect tree (all leaves vanish in the same round)
  • Duplicate values in different places

Hints

Hint 1

You could literally cut off the leaves, round after round, until the tree is empty.

Hint 2

In which round does a node disappear? Exactly after all its children are gone.

Hint 3

Define a node's height as 0 for a leaf and 1 + max(child heights) otherwise. The height is the index of the round it is removed in.

FAQ

What is the best time complexity for Find Leaves of Binary Tree?

Optimal (group by height in one postorder pass) runs in O(n) time and O(h) extra space. Each node is visited exactly once.

Which pattern does Find Leaves of Binary Tree use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.

Is there a brute force solution for Find Leaves of Binary Tree?

Yes. Brute force (strip leaves round by round) takes O(n · h) time and O(h) space. Repeat a DFS that detaches every current leaf and records its value, until the root itself has been removed.

Which edge cases should I test for Find Leaves of Binary Tree?

A single node; A chain (every round removes exactly one node); A perfect tree (all leaves vanish in the same round); Duplicate values in different places.