Find Leaves of Binary Tree

Find Leaves of Binary Tree

What is this problem about?

The Find Leaves of Binary Tree interview question asks you to collect and remove the leaf nodes of a binary tree in several "rounds." In each round, you find all the current leaf nodes, record their values, and then detach them from the tree. You repeat this until the tree is empty. The output should be a list of lists, where each sub-list contains the leaves removed in a specific round.

Why is this asked in interviews?

Companies like LinkedIn and Amazon use this to test your understanding of Tree Traversal and node height. The key insight is that a node's "round" of removal corresponds to its distance from the bottom of the tree. It evaluations your proficiency with the Depth-First Search (DFS) interview pattern and your ability to use recursive return values to determine a node's position relative to its descendants.

Algorithmic pattern used

This problem is elegantly solved using DFS based on Height.

1. Define the height of a leaf node as 0.
2. The height of any parent node is 1 + max(height(left), height(right)).
3. Notice that all nodes with the same height are removed in the same round.
4. As you perform a post-order DFS, calculate the height of each node.
5. Use the height as an index to add the node's value to the corresponding sub-list in your result.

Example explanation

Tree:

    1
   / 
  2   3
 / 
4   5

1. Nodes 4, 5, 3 are leaves (height 0). Round 1: [4, 5, 3].
2. Node 2's children are gone. Node 2 is now a leaf (height 1). Round 2: [2].
3. Node 1's children are gone. Node 1 is now a leaf (height 2). Round 3: [1]. Result: [[4, 5, 3], [2], [1]].

Common mistakes candidates make

• Actual Deletion: Trying to literally modify the tree structure and repeat the traversal multiple times, which results in $O(n^2)$ complexity.
• Confusion with depth: Using the distance from the root (depth) instead of the distance from the leaves (height).
• BFS approach: Attempting to use level-order traversal, which is difficult because removal happens from the bottom up, not top down.

Interview preparation tip

Height is the distance to the farthest leaf. Depth is the distance from the root. Recognizing when to use height vs depth is a fundamental part of the Binary Tree interview pattern. For bottom-up problems, always think about the height.