Find Leaves of Binary Tree - Solution & Explanation

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.