Cracking The Coding Interview Together – Problem 4.3: List of Depths

We've all encountered hierarchical data – file systems, organizational charts, or even the DOM of a web page. Binary trees are a fundamental way to model such structures in computer science. But what happens when we need to process or visualize this data not just as a single, interconnected entity, but specifically level by level? Imagine needing to display all employees at a certain management tier, or all files within a specific directory depth. This seemingly straightforward requirement introduces a subtle but important challenge: how do we efficiently group nodes based on their distance from the root?

This is precisely the core conflict we'll tackle today. We're not just traversing a tree; we're reorganizing its very structure into a series of distinct, depth-specific collections. Our shared goal is to design an algorithm that takes any binary tree and produces a list of linked lists, where each inner linked list contains all nodes found at a particular depth.

2. Problem Statement

The problem, often encountered in technical interviews, is stated as follows:

List of Depths: Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).

Our operational goals are clear:

• Process every node in the binary tree.
• For each unique depth level, create a new linked list.
• Populate that linked list with all nodes residing at that specific depth.
• Return a collection of these linked lists.

3. Analyze the Problem Together

Let's break this down. We're given a BinaryTree and need to return a List<LinkedList<TreeNode>>.

Constraints and Key Observations:

• Binary Tree: Each node has at most two children (left and right).
• Depth: The root is at depth 0. Its children are at depth 1, and so on.
• Output Structure: A list of linked lists. This implies we need to maintain an ordered collection of lists, where the index often corresponds to the depth.

The "Aha!" Conflict: How do we identify nodes at the same depth?

This is where the choice of traversal strategy becomes critical.

• Depth-First Search (DFS): If we use a standard DFS (pre-order, in-order, post-order), we naturally dive deep into one branch before exploring others. While we could pass a depth parameter down the recursive calls and use a Map<Integer, LinkedList<TreeNode>> to group nodes, managing the LinkedList creation and insertion can feel a bit less intuitive for level-by-level processing. We'd need to ensure the Map keys (depths) are processed in order to form the final List.
• Breadth-First Search (BFS): This is where BFS shines. BFS inherently explores a tree level by level. It processes all nodes at depth k before moving on to any nodes at depth k+1. This characteristic makes it a perfect fit for our problem.

Justifying Our Architectural Choice:

BFS, typically implemented with a queue, naturally provides us with nodes grouped by level. When we process a node, we add its children to the queue. By carefully tracking the size of the queue at the beginning of each level's processing, we can isolate all nodes belonging to that specific level. This direct mapping to the problem's requirement makes BFS the superior choice for clarity and efficiency in this scenario.

4. Questions for the Interviewer

As senior engineers, we always clarify ambiguities and explore edge cases. Here are a few questions we'd ask:

1. What should be returned if the input tree is empty or null? Should we return an empty list of linked lists, or null? (Typically, an empty list [] is preferred for consistency).
2. What kind of LinkedList implementation should we use for the inner lists? Are we expected to implement our own ListNode and LinkedList classes, or can we leverage standard library classes like java.util.LinkedList? (Using standard library is usually fine unless explicitly asked otherwise).
3. Are the node values unique? (Less critical for this specific problem, as we're dealing with TreeNode objects themselves, but good to understand the data's nature).
4. What are the expected constraints on the tree's size (number of nodes, maximum depth)? This helps us reason about potential memory usage and performance bottlenecks for very large trees.

For this solution, we'll assume an empty tree returns an empty List<LinkedList<TreeNode>>, and we'll use java.util.LinkedList for convenience.

5. Think About the Solution

Our high-level architecture will be a standard BFS traversal, augmented to track levels.

Core Components:

1. Queue<TreeNode>: This will be our workhorse for BFS. It will hold TreeNode objects waiting to be processed.
2. List<LinkedList<TreeNode>>: This will be our final result. Each LinkedList<TreeNode> inside this outer List will represent a single depth level.

Algorithm Steps (High-Level):

1. Initialize an empty List<LinkedList<TreeNode>> to store our results.
2. Initialize an empty Queue<TreeNode>.
3. If the root is null, return the empty results list immediately.
4. Add the root node to the queue.
5. While the queue is not empty:
   1. Get the current levelSize (the number of nodes currently in the queue). This levelSize represents all nodes at the current depth.
   2. Create a new LinkedList<TreeNode> to store nodes for this specific depth.
   3. Loop levelSize times:
      1. Dequeue a TreeNode from the queue.
      2. Add this dequeued node to the currentLevelList.
      3. If the dequeued node has a left child, enqueue it.
      4. If the dequeued node has a right child, enqueue it.
   4. After processing all nodes for the current level, add currentLevelList to our results list.
6. Return the results list.

Edge Cases to Consider:

• Empty Tree: Handled by checking root == null.
• Single Node Tree: The loop will run once. levelSize will be 1. The root will be dequeued, added to a list, and that list added to results. Queue becomes empty. Correct.
• Skewed Tree (e.g., only left children): BFS will still process level by level, correctly creating a new linked list for each node down the "skewed" path.

6. Write Code and Explain

Let's translate our thinking into production-ready Java code. We'll define a simple TreeNode class for clarity.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ListOfDepths {

    // Basic TreeNode class for our binary tree
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * Designs an algorithm to create a linked list of all the nodes at each depth
     * of a binary tree.
     *
     * @param root The root node of the binary tree.
     * @return A list of linked lists, where each inner linked list contains
     *         all nodes at a specific depth. Returns an empty list if the
     *         input tree is null.
     */
    public List<LinkedList<TreeNode>> createListOfDepths(TreeNode root) {
        // The main list to store all depth-specific linked lists.
        // We use ArrayList for the outer list as we'll be adding lists sequentially.
        List<LinkedList<TreeNode>> result = new ArrayList<>();

        // Handle the edge case of an empty tree immediately.
        if (root == null) {
            return result;
        }

        // A queue is essential for Breadth-First Search (BFS), which processes
        // nodes level by level. We'll store TreeNode objects directly.
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // Start BFS by adding the root node to the queue.

        // Continue as long as there are nodes to process in the queue.
        while (!queue.isEmpty()) {
            // At the start of each iteration, `levelSize` represents the number
            // of nodes currently at the *current* depth level.
            int levelSize = queue.size();

            // Create a new LinkedList to hold all nodes for the current depth.
            LinkedList<TreeNode> currentLevelList = new LinkedList<>();

            // Process all nodes at the current level.
            // We iterate `levelSize` times to ensure we only process nodes
            // that were present in the queue at the beginning of this level.
            for (int i = 0; i < levelSize; i++) {
                // Dequeue the next node from the front of the queue.
                TreeNode currentNode = queue.poll();
                // Add the dequeued node to our current level's linked list.
                currentLevelList.add(currentNode);

                // Enqueue the children of the current node for the next level.
                // These children will be processed in the *next* iteration of the while loop.
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            // After processing all nodes for the current level, add the
            // completed linked list for this level to our overall result.
            result.add(currentLevelList);
        }

        // Once the queue is empty, all nodes have been processed and grouped by depth.
        return result;
    }

    // --- Example Usage (for testing purposes) ---
    public static void main(String[] args) {
        // Construct a sample binary tree:
        //        1
        //       / \
        //      2   3
        //     / \   \
        //    4   5   6
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        ListOfDepths solver = new ListOfDepths();
        List<LinkedList<TreeNode>> depths = solver.createListOfDepths(root);

        // Print the results to verify
        System.out.println("List of Depths:");
        for (int i = 0; i < depths.size(); i++) {
            System.out.print("Depth " + i + ": ");
            for (TreeNode node : depths.get(i)) {
                System.out.print(node.val + " ");
            }
            System.out.println();
        }

        // Test with an empty tree
        System.out.println("\nTesting with empty tree:");
        List<LinkedList<TreeNode>> emptyDepths = solver.createListOfDepths(null);
        System.out.println("Result for empty tree (should be empty list): " + emptyDepths.isEmpty());

        // Test with a single node tree
        System.out.println("\nTesting with single node tree:");
        TreeNode singleNodeRoot = new TreeNode(100);
        List<LinkedList<TreeNode>> singleNodeDepths = solver.createListOfDepths(singleNodeRoot);
        System.out.println("Depth 0: " + singleNodeDepths.get(0).get(0).val);
    }
}

Step-by-Step Walkthrough:

1. Initialization: We create result (an ArrayList to hold our LinkedLists) and queue (a LinkedList acting as our BFS queue). If root is null, we immediately return an empty result.
2. Start BFS: We add the root node to our queue. This marks the beginning of processing depth 0.
3. Level-by-Level Processing (while (!queue.isEmpty())): This outer loop continues as long as there are nodes left to explore. Each iteration of this loop processes one complete level of the tree.
4. Capture levelSize: int levelSize = queue.size(); is the crucial step. At the start of a while loop iteration, queue.size() tells us exactly how many nodes are at the current depth. We store this because queue.size() will change as we add children.
5. Create currentLevelList: A new LinkedList<TreeNode> is instantiated for the nodes of the current depth.
6. Process Current Level Nodes (for (int i = 0; i < levelSize; i++)): This inner loop runs levelSize times, ensuring we only process nodes that belong to the current depth.
   • TreeNode currentNode = queue.poll();: We dequeue a node. This node is part of the current depth.
   • currentLevelList.add(currentNode);: We add this node to our currentLevelList.
   • if (currentNode.left != null) { queue.offer(currentNode.left); }: If the current node has a left child, we enqueue it. This child belongs to the next depth level.
   • if (currentNode.right != null) { queue.offer(currentNode.right); }: Similarly, we enqueue the right child if it exists.
7. Add to Results: After the inner for loop completes, currentLevelList now contains all nodes for the current depth. We add this currentLevelList to our result list.
8. Repeat: The while loop continues, and the next iteration will process the children we just enqueued, effectively moving to the next depth level.
9. Return: Once the queue is empty, all nodes have been visited, and result holds all the depth-specific linked lists.

7. Time & Space Complexity

Let's analyze the efficiency of our BFS-based solution.

• Time Complexity: O(N)
  • N represents the total number of nodes in the binary tree.
  • Every node in the tree is enqueued and dequeued exactly once.
  • For each node, we perform constant-time operations (checking for children, adding to a linked list).
  • Therefore, the total time complexity is directly proportional to the number of nodes.
• Space Complexity: O(N)
  • Queue: In the worst-case scenario (a complete binary tree), the queue might hold approximately N/2 nodes at the widest level. This contributes O(N) space.
  • Result List: The result list will store all N TreeNode objects across all its inner LinkedLists. This also contributes O(N) space.
  • Combining these, the dominant factor is O(N). For a skewed tree, the queue might only hold one node at a time, but the result list still holds all N nodes.

8. Why This Problem Matters (The Senior Perspective)

This "List of Depths" problem, while seemingly simple, is a fantastic illustration of fundamental data structure traversal and manipulation. From a senior engineering standpoint, it highlights several critical concepts:

• BFS as a Foundational Pattern: This problem is a classic application of Breadth-First Search. BFS isn't just for trees; it's crucial for graph traversals, finding the shortest path in unweighted graphs, and level-order processing in many domains. Understanding its mechanics is non-negotiable.
• Data Transformation: We're taking one data structure (a tree) and transforming it into another (a list of linked lists) based on a specific property (depth). This kind of data transformation is common in real-world systems, whether it's flattening a nested JSON structure, converting a database result set into a UI-friendly format, or aggregating logs.
• Resource Management (Memory): While O(N) space is often acceptable, for extremely large trees (e.g., millions of nodes), storing all nodes in memory at once (both in the queue and the result list) could become a concern. In such scenarios, we might consider:
  • Streaming/Iterators: If we only need to process one level at a time and don't need to retain all previous levels, we could design an iterator that yields LinkedList<TreeNode> objects, reducing peak memory usage.
  • External Storage: For truly massive trees that don't fit in memory, we might need to serialize levels to disk or a distributed cache.
• Concurrency and Immutability: If this tree were part of a concurrent system, we'd need to consider thread safety. Our current solution produces an immutable List<LinkedList<TreeNode>> once createListOfDepths completes, which is generally good. However, if the underlying TreeNode objects themselves could be modified by other threads during the traversal, we'd need proper synchronization or defensive copying.
• Architectural Implications: Imagine a UI component that displays a hierarchical menu. This algorithm could be used to generate the data for each menu level. Or, in a game, finding all enemies within a certain "hop" distance from the player (level-by-level search). It's a building block for more complex features.

This problem reinforces the idea that choosing the right algorithm for the job (BFS for level-order processing) can dramatically simplify implementation and improve clarity, even if the asymptotic complexity remains the same as a more convoluted DFS approach.

9. Final Thoughts

Mastering tree traversals is a cornerstone of becoming a proficient software engineer. The "List of Depths" problem is an excellent exercise in applying BFS effectively, demonstrating how a simple queue can elegantly manage complex hierarchical data. We've seen how to break down the problem, choose the optimal algorithm, implement it cleanly in Java, and analyze its performance characteristics.

As a next step, you might consider how you would solve this problem using a DFS approach. What additional parameters would your recursive function need? How would you manage the List<LinkedList<TreeNode>> to ensure nodes are added to the correct depth's list? This exploration will deepen your understanding of both traversal strategies and their trade-offs. Keep practicing, keep learning, and keep building!

Happy coding!