wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Set next node in a Binary Tree
        
(Message started by: amitkm on Mar 29^th, 2010, 11:53pm)

Title: Set next node in a Binary Tree
Post by amitkm on Mar 29^th, 2010, 11:53pm

I was asked this in an interview. Wtire code to set a next node between the 2 nodes of same lavel.

Example:
In the 2nd Level assuming 2 nodes the relation is L1-->R1
In a 3rd level assuming it has 4 leafs the relation is L2-->R2, R2-->L3, L3-->R4 and so on

Title: Re: Set next node in a Binary Tree
Post by towr on Mar 30^th, 2010, 1:49am

[hide]Use a queue to do a breadth first traversal, and be mindful not to put in a pointer from the last node in one level to the first node in the next.[/hide]

Title: Re: Set next node in a Binary Tree
Post by diptendubhowmick on Mar 31^st, 2010, 2:06am

We can do this by modified BFS in binary tree. Here init_q method returns a simple queue.

/*Inserts the children of a node in the queue*/
void insert_child(queue * q, tree * nd)
{
if(nd ==NULL)
return;
else
{
if (nd-> left != NULL)
q.enqueue(nd->left);
if(nd->right!=NULL)
q.enqueue(nd->right);
}
}

/*Main subroutine*/
void setNext(tree * root)
{
tree * nd = root;
queue * q1 = init_q();
queue * q2 = init_q();

insert_child(q1,nd);
while( q1 != NULL)
{
tree * cur_nd = q1->dequeue();
insert_child(q2,cur_nd);
while(q1 != NULL)
{
tree * next_nd = q1->dequeue();
cur_nd -> next = next_nd;
insert_child(q2,next_nd);
cur_nd = next_nd;
}
q1 = q2;
}
}

Summary: We are using two queues for keeping nodes for two levels separately. Like while traversing level 2, q1 will contains nodes of level 2 and q2 will contain nodes of level 3 (if any). We will take nodes from q1 one by only and link them because they are all in the same level. Once q1 is empty, it indicates that one level is over so we proceed to the next level.

Title: Re: Set next node in a Binary Tree
Post by bachelor on Mar 31^st, 2010, 10:24am

We can simply do normal BFS, in which we can keep a bit along with each node in queue.
This bit field keeps on flipping at every level.

Title: Re: Set next node in a Binary Tree
Post by towr on Mar 31^st, 2010, 1:00pm

I think using two queues is probably more efficient. 1 extra bit for every node adds up when a tree is large, and you need to check it every step. Whereas you can process the two queues in batch without additional checks.

Title: Re: Set next node in a Binary Tree
Post by amitkm on Mar 31^st, 2010, 3:24pm

Infact I suggested using the Queue with the extra field to keep the level. But the interviewer wanted not to use any extra DS, the hint was, use the next node already created to traverse the rest.

Title: Re: Set next node in a Binary Tree
Post by SMQ on Apr 1^st, 2010, 12:03pm

on 03/31/10 at 15:24:58, amitkm wrote:

[...] the hint was, use the next node already created to traverse the rest.

Nice!

template<typename T> struct TreeNode { T value; TreeNode *left, *right, *next; }; template<typename T> void setNextPointers(TreeNode<T> *root) { TreeNode *p = root, *prevNode = null, *nextLevel = null; if (root) root->next = null; while (p) { if (p->left) { if (!nextLevel) nextLevel = p->left; if (prevNode) prevNode->next = p->left; prevNode = p->left; } if (p->right) { if (!nextLevel) nextLevel = p->right; if (prevNode) prevNode->next = p->right; prevNode = p->right; } if (p->next) { p = p->next; } else { if (prevNode) prevNode->next = null; p = nextLevel; prevNode = nextLevel = null; } } }
--SMQ

Title: Re: Set next node in a Binary Tree
Post by kaka189 on Apr 2^nd, 2010, 12:32am

setnext(node * n,node * p)
{
if(n==null) return;
if(p == null) setnext (n->left,p)
else setnext(n->left,p->right);
setnext(n->right,n->left);
if(p!=null) p->right = n;
}

works for complete binary tree.