Create linked lists of all the nodes at each depth for a BST

Problem

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)

Example
So a binary tree such as :

       (1)  
      /   \\  
     /     \\  
   (2)     (3)  
  /  \\     / \\  
(4)  (5) (6) (7)

Will return linked lists:

(1) => NULL  
(2) => (3) => NULL  
(4) => (5) => (6) => (7) => NULL

Solution

Method 1 - Level order traversal
We just do a level-order traversal throughout the tree. For each level, create a linked list containing all the nodes at that depth. Then extract all of the children for each node to create the next linked list at deeper level.

public static ArrayList<LinkedList<BinaryTreeNode>> findLevelLinkList(  
        BinaryTreeNode root) {  
    int level = 0;  
    ArrayList<LinkedList<BinaryTreeNode>> result = new ArrayList<LinkedList<BinaryTreeNode>>();  
    LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>();  
    list.add(root);  
    result.add(level, list);  
    while (true) {  
        list = new LinkedList<BinaryTreeNode>();  
        for (int i = 0; i < result.get(level).size(); i++) {  
            BinaryTreeNode n = result.get(level).get(i);  
            if (n != null) {  
                if (n.getLeft() != null)  
                    list.add(n.getLeft());  
                if (n.getRight() != null)  
                    list.add(n.getRight());  
            }  
        }  
        if (list.size() > 0) {  
            result.add(level + 1, list);  
        } else {  
            break;  
        }  
        level++;  
    }  
    return result;  
}

Thanks.

See also