## Oracle Interview Question

Software Engineer / DevelopersTest case:

```
TNode root = null;
root = insert(root,100);
insert(root,200);
insert(root,50);
insert(root,25);
insert(root,75);
insert(root,250);
insert(root,150);
insert(root,10);
insert(root,8);
insert(root,6);
insert(root,4);
insert(root,300);
insert(root,400);
insert(root,500);
List<List<TNode>> result = treeToLinkList(root);
for(List<TNode> l : result){
for(TNode n: l){
System.out.print("->" + n.value);
}
System.out.println();
}
```

Output:

```
->100
->50->200
->25->75->150->250
->10->300
->8->400
->6->500
->4
```

How about this:

```
bfs(v)
{
Q = {v, dummy};
l = new list;
while (Q.size != 1) { // while Q does not contain any real vertex
v = Q.pop_front(); // remove the first node in the queue
if (v == dummy) {
output the list, and then clear it;
Q.push_back(dummy);
continue;
}
l.insert(v);
for (each child of v)
Q.push_back(v);
}
```

We can do an in-order traversal while maintaining the current depth so that we know to which list to add the current node. If we've never seen the current depth before, add a new list.

```
private void getNodesByDepthHelper (TreeNode root, int currentDepth, ArrayList<LinkedList<TreeNode>> depthLists)
{
if (root == null) { return; }
if (depthLists.size() == currentDepth)
{
depthLists.add (new LinkedList<TreeNode> ());
}
getNodesByDepthHelper (root.left, currentDepth+1, depthLists);
depthBuckets.get(currentDepth).add(root);
getNodesByDepthHelper (root.right, currentDepth+1, depthLists);
}
public ArrayList<LinkedList<TreeNode>> getNodesByDepth(TreeNode root)
{
ArrayList<LinkedList<TreeNode>> depthLists = new ArrayList<LinkedList<TreeNode>> ();
getNodesByDepthHelper (root, 0, depthLists);
return depthLists;
}
```

I liked your answer more than mine. But I was thinking that my approach can work on a Garph as well.

What do you think Eugene?

Breadth-first search algorithm using a dummy Node to divide each level (may not be necessary if we keep track of each level in a different way )

But this works just fine.

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> January 23, 2014