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.

Description Solution Video 17:45

366. Find Leaves of Binary Tree

Medium81.4% acceptance6 companiesPremium elsewhere, free here

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

Asked at 6 companies

Oracle LinkedIn Flipkart Salesforce

Google Amazon

Topics

17:45

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3,4,5]

Input

[1]

Your code is saved on this device.Solution