Question4_4.java

import java.util.LinkedList;

/**
 * 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).
 * 
 * Time  Complexity: O(n)
 * Space Complexity: O(n)
 */

public class Question4_4 {
    public LinkedList<LinkedList<TreeNode>> levelOrderTraversal(TreeNode root) {
        LinkedList<LinkedList<TreeNode>> traversal = new LinkedList<LinkedList<TreeNode>>();
        
        int currLevelNodes = 0;
        int nextLevelNodes = 0;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if (root != null) {
            queue.addFirst(root);
            ++nextLevelNodes;
        }
        
        while (!queue.isEmpty()) {
            if (currLevelNodes == 0) {
                currLevelNodes = nextLevelNodes;
                nextLevelNodes = 0;
                traversal.add(new LinkedList<TreeNode>());
            }
            
            TreeNode node = queue.removeLast();
            --currLevelNodes;
            traversal.getLast().add(node);
            if (node.left != null) {
                queue.addFirst(node.left);
                ++nextLevelNodes;
            }
            if (node.right != null) {
                queue.addFirst(node.right);
                ++nextLevelNodes;
            }
        }
        
        return traversal;
    }
    
    
    public static void main(String[] args) {
        Question4_4 question4_4 = new Question4_4();
        question4_4.levelOrderTraversal(null);
        
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(4);
        
        LinkedList<LinkedList<TreeNode>> traversal = question4_4.levelOrderTraversal(root);
        for (LinkedList<TreeNode> level : traversal) {
            for (TreeNode node : level) {
                System.out.print(node.value + "\t");
            }
            System.out.println();
        }
    }
}


class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode() {
        this(0, null, null);
    }
    
    public TreeNode(int value) {
        this(value, null, null);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}