Bloomberg LP Interview Question
Financial Software DevelopersAsutosh, when you do
buff[depth]->next = curr_node;
buff[depth] = curr_node;
Are you losing the pointer to the original buff[depth] pointer? i.e., you append a node the the tail of a list, but you then throw away the pointer to the previous tail... consequently, you can only retrieve the last node.
I think it should be
curr_node->next = buff[depth];
buff[depth] = curr_node;
i.e., insert to the head, and then you can traverse the list.
Let us say you tree is defined like this, where n is the variable that should point to its right neighbour
public static class Tree{
Tree left;
Tree right;
Tree n;
int value;
}
Then your code would be
public static void linkTreeLevels(Tree root){
Tree temp;
Tree head = null;
Tree node = null;
for(temp = root;temp!=null;temp = temp.n){
if(temp.left!=null){
if(head==null){
head = temp.left;
node = head;
}
else{
node.n = temp.left;
node = node.n;
}
}
if(temp.right!=null){
if(head == null){
head = temp.right;
node = head;
}
else{
node.n = temp.right;
node = node.n;
}
}
}
if(head!=null){
node.n = null;
linkTreeLevels(head);
}
}
Ashutosh solution is great!
A less efficient way would be to take two queues.
- Push root into the first queue
- Remove elements from the first queue, chaining them together and pushing their children into the second queue as they are being removed.
- Now remove elements from the second queue, chaining them together and pushing their children into first queue.
- So on until queues are empty.
ArrayList<LinkedList<BinaryNode>> findlevelbylevel(BinaryNode root)
{
ArrayList<LinkedList<BinaryNode>> result = new ArrayList<LinkedList<BinaryNode>>();
LinkedList<BinaryNode> list = new LinkedList<BinaryNode>();
list.Add(root);
result.Add(list);
int level=0;
While (true)
{
list = new LinkedList<BinaryNode>();
for (int i=0;i<result.get(level).size();i++
{
BinaryNode node = result.get(level).get(i);
if (node.left!=null)
list.Add(node.left);
if (node.right!=null)
list.Add(node.right);
}
if (list.size()>0)
result.Add(list);
else
break;
level++;
}
return result;
}
- Ashutosh February 01, 2010