Find Leaves of Binary Tree
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
1to100nodes. -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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n · h)There are h + 1 rounds (h = tree height) and each round walks the remaining tree, up to n nodes.O(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.
- While root is not null: start an empty round list.
- 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.
- 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;
}
}class Solution:
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
while root is not None:
round_vals = []
root = self.strip(root, round_vals)
res.append(round_vals)
return res
def strip(self, node: Optional[TreeNode], round_vals: List[int]) -> Optional[TreeNode]:
if node is None:
return None
if node.left is None and node.right is None:
round_vals.append(node.val)
return None
node.left = self.strip(node.left, round_vals)
node.right = self.strip(node.right, round_vals)
return nodeclass Solution {
public:
vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> res;
while (root != nullptr) {
vector<int> round;
root = strip(root, round);
res.push_back(round);
}
return res;
}
private:
TreeNode* strip(TreeNode* node, vector<int>& round) {
if (node == nullptr) return nullptr;
if (node->left == nullptr && node->right == nullptr) {
round.push_back(node->val);
return nullptr;
}
node->left = strip(node->left, round);
node->right = strip(node->right, round);
return node;
}
};function findLeaves(root) {
const res = [];
const strip = (node, round) => {
if (node === null) return null;
if (node.left === null && node.right === null) {
round.push(node.val);
return null;
}
node.left = strip(node.left, round);
node.right = strip(node.right, round);
return node;
};
while (root !== null) {
const round = [];
root = strip(root, round);
res.push(round);
}
return res;
}2Optimal (group by height in one postorder pass)
O(n)Each node is visited exactly once.O(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.
- height(null) = -1.
- h = 1 + max(height(left), height(right)).
- If res has only h lists, append a new one; then res[h].add(node.val).
- 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;
}
}class Solution:
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
def height(node: Optional[TreeNode]) -> int:
if node is None:
return -1
h = 1 + max(height(node.left), height(node.right))
if len(res) == h:
res.append([])
res[h].append(node.val)
return h
height(root)
return resclass Solution {
public:
vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> res;
height(root, res);
return res;
}
private:
int height(TreeNode* node, vector<vector<int>>& res) {
if (node == nullptr) return -1;
int left = height(node->left, res);
int right = height(node->right, res);
int h = 1 + max(left, right);
if ((int) res.size() == h) res.push_back({});
res[h].push_back(node->val);
return h;
}
};function findLeaves(root) {
const res = [];
const height = (node) => {
if (node === null) return -1;
const h = 1 + Math.max(height(node.left), height(node.right));
if (res.length === h) res.push([]);
res[h].push(node.val);
return h;
};
height(root);
return res;
}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.