Amazon Interview Question Software Engineer / Developers
pseudocode:
void f(treenode *root){
if(root==NULL) return;
queue q;
q.enqueue(root);
treenode *p=NULL
q.enqueue(p);
while( !q.empty()){
p=q.dequeue();
if(p==NULL&& p.front()!=NULL){
q.enqueue(p);
continue;
}
else{
if (p.left!=NULL) q.enqueue(p.left);
if (p.right!=NULL) q.enqueue(p.right);
}
p.next=q.front();
}
}
algorithm:
1. Maintain a queue of node pointers at the same level.
while(q is not empty)
{
2. Iterate through the queue and set the next pointers to point to the next node in the queue. The last node in the queue will point to NULL.
3. Iterate through the queue, dequeue a node and enqueue its left and right children if they exist.
}
algorithm:
1. Maintain a queue of node pointers at the same level.
while(q is not empty)
{
2. Iterate through the queue and set the next pointers to point to the next node in the queue. The last node in the queue will point to NULL.
3. Iterate through the queue, dequeue a node and enqueue its left and right children if they exist.
}
Here is the code...
void link(node* root)
{
queue q;
if(root==NULL) return;
root->next=NULL;
if(root->left)
q.enqueue(root->left);
if(root->right)
q.enqueue(root->right);
while(!q.empty())
{
node* prev = NULL;
Iter iter(q);
for(iter.begin(); !iter.end(); iter++)
{
void link(node* root)
{
queue q;
if(root==NULL) return;
root->next=NULL;
if(root->left)
q.enqueue(root->left);
if(root->right)
q.enqueue(root->right);
while(!q.empty())
{
node* prev = NULL;
Iter iter(q);
for(iter.begin(); !iter.end(); iter++)
{
if(!prev)
prev = *iter;
else{
prev->next = *iter;
prev = prev->next;
}
}
prev->next=NULL;
Iter iter(q);
for(iter.begin();!iter.end();iter++)
{
q.dequeue();
if(*iter->left)
q.enqueue(*iter->left);
if(*iter->right)
q.enqueue(*iter->right);
}
}
/*
* The idea is to use to use 2 queues.
* One queue will hold all Node references at one level while the other one will hold Node references at the next level
* Of course, it is less efficient that other programs. But the code looks elegant
*/
public void populateNext(Node root){
Queue<Node> q1 = new LinkedList<Node>();
Queue<Node> q2 = new LinkedList<Node>();
q1.add(root);
while ( !q1.isEmpty()) {
Node temp = q1.remove();
temp.next = q1.peek();
if ( temp.left != null)
q2.add(temp.left);
if ( temp.right != null)
q2.add(temp.right);
if ( q1.isEmpty()) {
while (!q2.isEmpty()) {
q1.add(q2.remove());
}
}
}
}
pseudocode:
- Anonymous February 07, 2010void f(treenode *root){
if(root==NULL) return;
queue q;
q.enqueue(root);
treenode *p=NULL
q.enqueue(p);
while( !q.empty()){
p=q.dequeue();
if(p==NULL&& p.front()!=NULL){
q.enqueue(p);
continue;
}
else{
if (p.left!=NULL) q.enqueue(p.left);
if (p.right!=NULL) q.enqueue(p.right);
}
p.next=q.front();
}
}
treenode *pn;
}
}