## Monday, February 10, 2014

### 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)
```

```(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;
while (true) {
for (int i = 0; i < result.get(level).size(); i++) {
BinaryTreeNode n = result.get(level).get(i);
if (n != null) {
if (n.getLeft() != null)
if (n.getRight() != null)
}
}
if (list.size() > 0) {
} else {
break;
}
level++;
}
return result;
}
```

Thanks.