Knowledge Guide
Home › DSA › Company Practice

medium Find Leaves of Binary Tree

Problem Statement

Given the root of a binary tree, collect a tree's leaf nodes by following the given rules and return them in a 2D array.

Examples

Image
Image
Image
Image
Image
Image

Try it yourself

Try solving this question here:

✅ Solution Find Leaves of Binary Tree

Problem Statement

Given the root of a binary tree, collect a tree's leaf nodes by following the given rules and return them in a 2D array.

  • Collect all the leaf nodes from the left to right.
  • Remove all the leaf nodes.
  • Repeat until the tree is empty.

Examples

  • Example 1:
    • Input: root = [1,2,3,4]
Image
Image

  • Expected Output: [[4,3],[2],[1]]

  • Justification: Initially, nodes 4 and 3 are leaves and are removed in the first round. In the second round, node 2 becomes a leaf. Node 1 is the last one remaining and is removed in the final round.

  • Example 2:

    • Input: root = [1,2,3,null, null,4,5,null, null,6,null]
Image
Image

  • Expected Output: [[2,4,6],[5],[3],[1]]

  • Justification: In the first round, the leaves are nodes 2, 4, and 6. Once removed, node 5 becomes the leaf in the second round, and then node 3 becomes the leaf node in the third round. Finally, node 1 is left and removed in the last round.

  • Example 3:

    • Input: root = [1,2,null,3,null,4]
Image
Image
  • Expected Output: [[4],[3],[2],[1]]
  • Justification: This tree has a linear structure. Each node becomes a leaf one after the other, starting from node 4 to node 1.

Solution

To solve this problem, we employ a depth-first search (DFS) strategy to identify the leaves of the binary tree at each level. The key idea is to traverse the tree from the bottom up. This approach allows us to determine the "height" of each node, with the height of a leaf being 0. The height of a node is the number of edges on the longest downward path between that node and a leaf. By calculating these heights during our DFS traversal, we can group nodes with the same height together, as they will be removed in the same round.

This method is effective because it leverages the natural structure of a binary tree to minimize the amount of work needed to identify leaves at each round. By using the height of nodes as a guide, we avoid the need to repeatedly traverse the entire tree to find leaves. Additionally, this approach ensures that our solution is scalable and can handle trees of various sizes and shapes efficiently.

Step-by-Step Algorithm

  1. Implement the DFS Function:

    • Define a recursive function dfs that takes a TreeNode and returns its height. The height of a null node is considered -1. This function performs several key operations:
      • It first checks if the current node is null. If so, it returns -1.
      • It recursively calls itself for the left and right children of the current node to calculate their heights.
      • It calculates the current node's height as the maximum of its children's heights plus one.
      • It adds the current node's value to the appropriate sublist in the list of leaves, based on the current node's height. If the sublist for the current height doesn't exist, it creates a new sublist.
      • It returns the current node's height.

  2. Find Leaves of the Binary Tree:

    • Define the main function findLeaves that takes the root of the binary tree. This function initializes the list of leaves and calls the dfs function with the root node.
    • The dfs function populates the list with leaves grouped by their removal rounds as it traverses the tree.
    • Finally, the findLeaves function returns the list of leaves.

Algorithm Walkthrough

Let's consider the Input: root = [1,2,3,null,null,4,5,null,null,6,null]

        1
       / \
      2   3
         / \
        4   5
           /
          6

  1. Start DFS with Root Node 1:

    • The root node 1 is not a leaf. We proceed with its children.

  2. Traverse to the Left Child 2 of Root Node 1:

    • Node 2 is a leaf node (no children).
    • It's added to leaves[0] since its height from the bottom is 0.
    • The list now looks like [[2]].

  3. Backtrack to Node 1 and Traverse to the Right Child 3:

    • Node 3 is not a leaf. We proceed with its children.

  4. Traverse to the Left Child 4 of Node 3:

    • Node 4 is a leaf node.
    • It's added to leaves[0], updating the list to [[2, 4]].

  5. Traverse to the Right Child 5 of Node 3:

    • Node 5 is not a leaf. We proceed with its child.

  6. Traverse to the Left Child 6 of Node 5:

    • Node 6 is a leaf node.
    • It's added to leaves[0], updating the list to [[2, 4, 6]].

  7. Backtrack to Node 5 After Removing 6:

    • Now, Node 5 becomes a leaf.
    • It's height from the bottom is 1 (since it was one level above 6).
    • It's added to leaves[1], updating the list to [[2, 4, 6], [5]].

  8. Backtrack to Node 3 After Removing Its Children (4 and 5):

    • Node 3 now becomes a leaf.
    • Its height from the bottom is 2.
    • It's added to leaves[2], updating the list to [[2, 4, 6], [5], [3]].

  9. Backtrack to Root Node 1 After Removing Its Children:

    • Finally, the root node 1 becomes the last leaf to be removed.
    • Its height from the bottom is 3.
    • It's added to leaves[3], completing the list as [[2, 4, 6], [5], [3], [1]].

Code

java
import java.util.ArrayList;
import java.util.List;

// TreeNode class representing a node in a binary tree
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  // Method to calculate the height of each node and group leaves by their removal rounds
  private int dfs(TreeNode node, List<List<Integer>> leaves) {
    if (node == null) return -1; // Base case: If node is null, return -1 indicating height -1
    // Recursively calculate the heights of left and right subtrees
    int leftHeight = dfs(node.left, leaves);
    int rightHeight = dfs(node.right, leaves);
    // Calculate the current node's height as the maximum of left and right subtree heights plus 1
    int currHeight = Math.max(leftHeight, rightHeight) + 1;
    // If the list of leaves doesn't have a list at the current height, create a new list
    if (leaves.size() <= currHeight) leaves.add(new ArrayList<>());
    // Add the current node's value to the list of leaves at the current height
    leaves.get(currHeight).add(node.val);
    return currHeight; // Return the current height
  }

  // Method to find and group leaves by their removal rounds
  public List<List<Integer>> findLeaves(TreeNode root) {
    List<List<Integer>> leaves = new ArrayList<>(); // Initialize a list to store leaves
    dfs(root, leaves); // Call the dfs method to find and group leaves
    return leaves; // Return the list of grouped leaves
  }

  // Testing the solution with the given example
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Constructing the binary tree from the example
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.right.left = new TreeNode(4);
    root.right.right = new TreeNode(5);
    root.right.right.left = new TreeNode(6);

    // Expected output: [[2,4,6],[5],[3],[1]]
    List<List<Integer>> result = solution.findLeaves(root); // Find and group leaves
    System.out.println(result); // Print the result
  }
}

Complexity Analysis

Time Complexity

  • DFS Traversal: The Depth-First Search (DFS) algorithm visits each node exactly once. Therefore, the time complexity is , where (N) is the number of nodes in the binary tree.

Space Complexity

  • Recursive Stack: The DFS algorithm uses a recursive stack. In the worst case (a skewed tree), the height of the recursion tree can be , leading to a space complexity of .
  • Output List: The space taken by the output list is since every node is stored in the list exactly once.
  • Combined: Considering both the recursive stack and the output list, the overall space complexity remains .
🤖 Don't fully get this? Learn it with Claude

Stuck on Find Leaves of Binary Tree? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Find Leaves of Binary Tree** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Find Leaves of Binary Tree** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Find Leaves of Binary Tree**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Find Leaves of Binary Tree**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Diagonal TraverseShortest Path in Binary Matrix →