Skip to main content
Talentd

Find Leaves of Binary Tree - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBinary Tree6 min readAsked at: Amazon, Oracle, Salesforce +3
Practice this problem

Problem Statement

Given the root of a binary tree, collect a tree's nodes as if you were doing this:

  • Collect all the leaf nodes.
  • Remove all the leaf nodes.
  • Repeat until the tree is empty.

 

Example 1:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Example 2:

Input: root = [1]
Output: [[1]]

 

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • -100 <= Node.val <= 100

Approach Overview

Problem Overview: Given the root of a binary tree, repeatedly collect all leaf nodes and remove them from the tree until the tree becomes empty. The result should group leaves by the round in which they are removed. The first list contains the original leaves, the second contains leaves after the first removal, and so on.

Approach 1: Repeated Leaf Removal Simulation (O(n^2) time, O(n) space)

The most direct strategy simulates the process described in the problem. Traverse the tree, collect all nodes with no children, remove them, and repeat until the tree is empty. Each round requires a full traversal to identify leaves, which costs O(n). In the worst case (such as a skewed tree), you may repeat this process up to n times, leading to O(n^2) time complexity with O(n) space for storing results and recursion. This approach is easy to reason about but inefficient for large trees.

Approach 2: DFS Height Grouping (O(n) time, O(n) space)

A more efficient observation: the round when a node becomes a leaf depends on its height from the bottom of the tree. Leaves have height 0, their parents have height 1, and so on. Run a postorder traversal using Depth-First Search. For each node, compute height = 1 + max(leftHeight, rightHeight). Append the node value to the result list at index height. Since each node is processed exactly once, the traversal runs in O(n) time with O(n) space for recursion and result storage. This method converts the repeated-removal process into a single pass over the binary tree.

Approach 3: Topological Layering with Parent Map (O(n) time, O(n) space)

Another perspective treats the tree like a graph peeling problem. Build a parent map and track the number of children for each node. Start by pushing all leaves into a queue. Remove them layer by layer, decreasing the child count of their parents. When a parent’s remaining child count becomes zero, it becomes a leaf in the next round. This behaves similarly to topological sorting on a tree structure. The algorithm processes each node and edge once, giving O(n) time and O(n) extra memory.

Recommended for interviews: The DFS height-based solution is the one most interviewers expect. It demonstrates strong understanding of tree recursion and postorder traversal while achieving optimal O(n) complexity. Mentioning the brute-force simulation first shows you understand the problem statement literally, but deriving the height insight shows deeper algorithmic thinking.

Solution

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Leaf Removal SimulationO(n^2)O(n)Conceptual baseline when first reasoning about the problem
DFS Height GroupingO(n)O(n)Best general solution; single traversal using postorder DFS
Topological Layering with Parent MapO(n)O(n)Useful when thinking in graph terms or implementing iterative BFS-style logic

Video Solution

Find Leaves Of Binary Tree | Google Onsite 2022 | Amazon | codestorywithMIK • codestorywithMIK • 12,977 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Leaves of Binary Tree easy or hard?
Find Leaves of Binary Tree is generally classified as a medium-level tree problem. The brute-force interpretation is straightforward, but recognizing that leaf-removal rounds correspond to node heights requires deeper understanding of postorder DFS. Once that insight is clear, the implementation becomes relatively concise.
Find Leaves of Binary Tree Python/Java solution
Most implementations use a recursive DFS helper that returns the height of each node. When visiting a node, compute the height from its children and append the node value to result[height]. The same logic works across Python, Java, C++, Go, TypeScript, and C# with minor syntax differences.
How to solve Find Leaves of Binary Tree in O(n)?
Perform a postorder DFS and compute the height of each node from the bottom. For each node, calculate height = 1 + max(leftHeight, rightHeight). Use the height as the index in the result list and append the node value there. Since each node is processed once and each height is computed in constant time, the total complexity is O(n).
What is the best approach for Find Leaves of Binary Tree?
The most efficient solution uses a postorder DFS that groups nodes by their height from the bottom of the tree. Leaves have height 0, their parents have height 1, and so on. During traversal you compute the height of each node and append it to the corresponding result list. This approach processes each node once, giving O(n) time and O(n) space complexity.
Is Find Leaves of Binary Tree asked at Google/Amazon/Meta?
Tree traversal and DFS-based grouping problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. Variations that require computing node heights, removing layers of leaves, or processing trees level-by-level are frequently used to evaluate recursion and tree reasoning skills.
What data structure is used in Find Leaves of Binary Tree?
The core data structure is a binary tree combined with recursion for depth-first traversal. The optimal solution uses a dynamic list (or array of lists) to store nodes grouped by height. Some alternative implementations also use a queue and parent map to simulate topological leaf removal.
What is the time complexity of Find Leaves of Binary Tree?
The optimal DFS height-based solution runs in O(n) time because every node is visited exactly once during the postorder traversal. Space complexity is O(n) due to recursion stack and the result list storing all nodes grouped by height. A naive repeated-removal simulation can degrade to O(n^2) time in skewed trees.

Ready to solve this problem?

Practice Find Leaves of Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II