Author |
Topic: Set next node in a Binary Tree (Read 1792 times) |
|
amitkm
Newbie
Posts: 3
|
 |
Set next node in a Binary Tree
« on: Mar 29th, 2010, 11:53pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Set next node in a Binary Tree
« Reply #1 on: Mar 30th, 2010, 1:49am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
diptendubhowmick
Newbie
Posts: 11
|
|
Re: Set next node in a Binary Tree
« Reply #2 on: Mar 31st, 2010, 2:06am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
bachelor
Newbie
Posts: 2
|
|
Re: Set next node in a Binary Tree
« Reply #3 on: Mar 31st, 2010, 10:24am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 31st, 2010, 10:25am by bachelor » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Set next node in a Binary Tree
« Reply #4 on: Mar 31st, 2010, 1:00pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
amitkm
Newbie
Posts: 3
|
|
Re: Set next node in a Binary Tree
« Reply #5 on: Mar 31st, 2010, 3:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Set next node in a Binary Tree
« Reply #6 on: Apr 1st, 2010, 12:03pm » |
Quote Modify
|
on Mar 31st, 2010, 3:24pm, 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
|
| « Last Edit: Apr 1st, 2010, 12:36pm by SMQ » |
IP Logged |
--SMQ
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Set next node in a Binary Tree
« Reply #7 on: Apr 2nd, 2010, 12:32am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print