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

        riddles >> cs >> bst2dll
        
(Message started by: ic10503 on Jul 31st, 2008, 3:57am)
Title: bst2dll
Post by ic10503 on Jul 31st, 2008, 3:57am
I know that this problem is there in this forum, but i could not get the code or description for it.
Sorry if it is irritating.

Please paste the link for converting a binary search tree into doubly linked list(not a circular one)..

Thanks
Title: Re: bst2dll
Post by nks on Jul 31st, 2008, 4:23am
Here are the steps:
Use Post fix traversal of BST
keep calling function written below.
write a function to change the link of receved link.
 like dl(node * p){
if (q){
p->right =q;
 q->left =p;
}

else
q= p;
}
q will be null initally
Title: Re: bst2dll
Post by inexorable on Jul 31st, 2008, 4:47am
sorted dll to bst was discussed but I don't think code for bst to dll was discussed.

Code:
node * Tree :: convLnLst(node *T,int flag=-1){
node *l1,*l2;

if(T!=NULL){
l1=convLnLst(T->left,0);
l2=convLnLst(T->right,1);

T->left=l1;
T->right=l2;

if(l1!=NULL){
l1->right=T;
}

if(l2!=NULL){
l2->left=T;
}
if(flag==0 && T->right)
return T->right;

if(flag==1 && T->left)
return T->left;

if(flag==-1){
while(T->left)
T=T->left;
}

}
return T;
}

call the function as convLnLst(T)
Title: Re: bst2dll
Post by ic10503 on Jul 31st, 2008, 5:35am

on 07/31/08 at 04:47:24, inexorable wrote:
sorted dll to bst was discussed but I don't think code for bst to dll was discussed.

Code:
node * Tree :: convLnLst(node *T,int flag=-1){
node *l1,*l2;

if(T!=NULL){
l1=convLnLst(T->left,0);
l2=convLnLst(T->right,1);

T->left=l1;
T->right=l2;

if(l1!=NULL){
l1->right=T;
}

if(l2!=NULL){
l2->left=T;
}
if(flag==0 && T->right)
return T->right;

if(flag==1 && T->left)
return T->left;

if(flag==-1){
while(T->left)
T=T->left;
}

}
return T;
}

call the function as convLnLst(T)



Can you please explain what exactly are you trying to do in the code?
Thank you
Title: Re: bst2dll
Post by inexorable on Aug 1st, 2008, 12:23am

on 07/31/08 at 05:35:42, ic10503 wrote:
Can you please explain what exactly are you trying to do in the code?
Thank you

A sorted doubly linked list is created from bst in O(n) time
For each node in the bst the left is made to point to previous element in dll and right is made to point to next element in dll.
Flag is used to keep track if a node is left child or right child of parent.
function call on left subtree returns rightmost child and viceversa.
Finally the first function call returns the first element in dll.
Title: Re: bst2dll
Post by gt on Jul 4th, 2009, 2:16am
can this be done without using any auxiliary data structure...like without using any recursion or a user stack.....
Title: Re: bst2dll
Post by towr on Jul 4th, 2009, 2:32am

on 07/04/09 at 02:16:02, gt wrote:
can this be done without using any auxiliary data structure...like without using any recursion or a user stack.....
Yes, but not as fast.
Start at the root, if there is a right child, go to its right-most descendant and link it to the left subtree, then move the right subtree to the left. Then move to the next node and repeat.
Title: Re: bst2dll
Post by ONS on Jul 8th, 2009, 12:13am
i am unable to understand the question. do we have to generate a sorted dll?
does each 'next' points to its successor in bst and each 'prev' points to its predecessor?
Title: Re: bst2dll
Post by towr on Jul 8th, 2009, 1:07am

on 07/08/09 at 00:13:30, ONS wrote:
i am unable to understand the question. do we have to generate a sorted dll?
does each 'next' points to its successor in bst and each 'prev' points to its predecessor?
http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml#BST2LL
Title: Re: bst2dll
Post by alphare on Oct 14th, 2009, 2:56pm
ic10503, nks,

Both of your solutions are not correct.
Anyone think it can be done in O(1) space>
Title: Re: bst2dll
Post by towr on Oct 14th, 2009, 3:08pm

on 10/14/09 at 14:56:23, alphare wrote:
Anyone think it can be done in O(1) space>
Sure. You can traverse a tree in O(1) space, if you try hard enough (and are allowed to abuse the pointers in the tree to arrange the necessary administration). Which means you can put the nodes in a double linked list while doing so.
Title: Re: bst2dll
Post by Grimbal on Oct 15th, 2009, 3:16pm
node *bsd2dll(node *root){
 node *tail = NULL;
 for( node *p = root ; p ; p = p->left ){
   node *q;
   while( (q = p->right) ){
     p->right = q->left;
     q->left = p;
     p = q;
   }
   p->right = tail;
   if( tail ) tail->left = p;
   tail = p;
 }
 return tail;
}

edit:code fixed
Title: Re: bst2dll
Post by alphare on Oct 15th, 2009, 11:38pm
this one is incorrect either...


on 10/15/09 at 15:16:52, Grimbal wrote:
node *bsd2dll(node *root){
 node *tail = NULL;
 for( node *p = root ; p ; p = p->left ){
   node *q;
   while( (q = p->right) ){
     p->right = q->left;
     q->left = p;
     p = q;
   }
   p->right = tail;
   tail = p;
 }
 return tail;
}
Title: Re: bst2dll
Post by towr on Oct 16th, 2009, 12:50am
You know, unless you say why they are supposedly incorrect, it's not a very convincing statement.
Title: Re: bst2dll
Post by alphare on Oct 16th, 2009, 1:25am
Sorry, I should elaborated the results.
Try bst 1,2,3,4,5,7,8,9 rooted at 7. Run the algorithm do returns a dll starting from 1 to 9. But only the single ll 1->9 is correct, 9->1 is incorrect. For example, the prev of 4 is 2, which is obviously wrong.

The reason why I doubt there is no O(1) space solution is that even you can traverse a bst in O(1) space, but you have to remember the left leafs' precedents as well as right leafs' successors, you can not change the bst such that both the traverse procedure is guaranteed  and the points of each node are set to make a dll.



on 10/16/09 at 00:50:53, towr wrote:
You know, unless you say why they are supposedly incorrect, it's not a very convincing statement.
Title: Re: bst2dll
Post by alphare on Oct 16th, 2009, 1:29am
OK, traverse the link list of Grimbal again and fix the prev problem do yield a solution that is O(1) space.  ;D



on 10/16/09 at 00:50:53, towr wrote:
You know, unless you say why they are supposedly incorrect, it's not a very convincing statement.
Title: Re: bst2dll
Post by Grimbal on Oct 16th, 2009, 11:52am

on 10/15/09 at 23:38:59, alphare wrote:
this one is incorrect either...

Oops... right.  Code fixed.  I hope.
Title: Re: bst2dll
Post by alphare on Oct 16th, 2009, 12:04pm
Yeah, It works fine. Cheers...  :)

on 10/16/09 at 11:52:29, Grimbal wrote:
Oops... right.  Code fixed.  I hope.
Title: Re: bst2dll
Post by brute on Dec 2nd, 2009, 6:23am
alphare wrote:
ic10503, nks,

Both of your solutions are not correct.

whats exactly wrong with the code given by nks, could not understand the reply given by alphare.......  :-[
Title: Re: bst2dll
Post by nks on Dec 3rd, 2009, 1:39am
I have modified the code and tested it for some inputs. But this is not in sorted order.
It is using recursion. check it .

BNODE *  btodll(BNODE * root)
{
 static BNODE *r = NULL;
 if(root) {
 btodll(root->left);
 btodll(root->right);

 if((r!=root)&&(r))
 {
   r->right=root;
   root->left=r;
 }
 r=root;
}
return r;

}
Title: Re: bst2dll
Post by birbal on Jan 12th, 2010, 11:04pm

on 07/31/08 at 04:47:24, inexorable wrote:
sorted dll to bst was discussed but I don't think code for bst to dll was discussed.


Code:
node * Tree :: convLnLst(node *T,int flag=-1){

node *l1,*l2;



if(T!=NULL){

l1=convLnLst(T->left,0);

l2=convLnLst(T->right,1);



T->left=l1;

T->right=l2;



if(l1!=NULL){

l1->right=T;

}



if(l2!=NULL){

l2->left=T;

}

if(flag==0 && T->right)

return T->right;



if(flag==1 && T->left)

return T->left;



if(flag==-1){

while(T->left)

T=T->left;

}



}

return T;

}


call the function as convLnLst(T)




in this code

if(flag==0 && T->right)

return T->right;





what if t->right is a list of more than one element ?

since it is left subtree of the parent, you have to return rightmost element.

shouldnt it be


Code:
if(flag==0)

{

     while(T->right)

           T=T->right;

     return T;

}


similarly for right subtree
Title: Re: bst2dll
Post by blackJack on Apr 10th, 2010, 11:36am

Quote:

what if t->right is a list of more than one element ?

since it is left subtree of the parent, you have to return rightmost element.


No, recursion will take care of that. I mean to say, t-> right will return the right most element of its own subtree.
Title: Re: bst2dll
Post by AB on Apr 22nd, 2010, 12:28am
Hi can we do a simple in-order traversal and link the node->right pointer to the next node every time. Correct me if i am wrong.. :-X
Title: Re: bst2dll
Post by birbal on May 31st, 2010, 2:47am

on 04/22/10 at 00:28:47, AB wrote:
Hi can we do a simple in-order traversal and link the node->right pointer to the next node every time. Correct me if i am wrong.. :-X


Yes, i think you can use a queue to store the nodes while doing in-order traversal. Then you can process the queue make a doubly linked list of nodes.

Also you need only fixed size memory for the queue. Since you can conv it to list after addding each node.

something like this

Code:
Queue q

conv_lst(Node T)
{
  conv_lst(T->left);
  q.push(T);
  process_queue();
  conv_lst(T->right);
}

Node root;
process_queue()
{
if(q.size() ==1 )
  root = q.top();
if(q.size() > 2)
{
   Node curr = q.deq();
   curr->right = t.top();
   q.top()->left = curr;
}
}


You will need fixed memory for the queue :)
Title: Re: bst2dll
Post by birbal on Jul 24th, 2010, 11:48pm

on 04/10/10 at 11:36:48, blackJack wrote:
No, recursion will take care of that. I mean to say, t-> right will return the right most element of its own subtree.

I am still unconvinced :( ....please explain a bit more
try to run it on a tree like this
  1
2
 3
4   5
(1 is root, 2 is its left child having a right subtree )
convLnLst( 1 )
|--L1 = convLnLst(2 , 0);
      |---L2 = convLnLst(3 , 1);
Here L2 = 4 after execution of convLnLst(3 , 1);
then
2->right = 4;
4->left = 2;
return 2->right (which is 4)
hence
1->left = 4;
(which should be 5)
please explain
Title: Re: bst2dll
Post by Grimbal on Jul 26th, 2010, 2:44am
Using recursion, you can do something like this.

node* convert(root){
 convert(null, root, null);
 while( root && root->left ) root = root->left;
 return root;
}
void convert(leftEnd, node, rightEnd){
 if( node ){
   convert(leftEnd, node->left, node);
   convert(rightEnd, node->right, node);
 } else {
   if( leftEnd ) leftEnd->right = rightEnd;
   if( rightEnd ) rightEnd->left = leftEnd;
 }
}

edit: code fixed.
Title: Re: bst2dll
Post by birbal on Jul 26th, 2010, 6:19am

on 07/26/10 at 02:44:19, Grimbal wrote:
Using recursion, you can do something like this.

void convert(root){
 convert(null, root, null);
}
void convert(leftEnd, node, rightEnd){
 if( node ){
   convert(leftEnd, node->left, node);
   convert(rightEnd, node->right, node);
 } else {
   if( leftEnd ) leftEnd->right = rightEnd;
   if( rightEnd ) rightEnd->left = leftEnd;
 }
}

Yes, we can just pass on the end pointers instead of iterating through the whole list.

But my concern is different :| ....is that code wrong ?
Title: Re: bst2dll
Post by Grimbal on Jul 27th, 2010, 12:54am
You are right.  Inexorable's convLnLst doesn't return the right node.  (As a matter of fact, my code has the same problem...).

A better code would be:
node * Tree :: convLnLst(node *T, int flag=1){
 node *l1,*l2;
 if(T!=NULL){
  l1=convLnLst(T->left,0);
  l2=convLnLst(T->right,1);
  T->left=l1;
  T->right=l2;
  if(l1!=NULL){
   l1->right=T;
 }
  if(l2!=NULL){
  l2->left=T;
  }
  if(flag==1){
   while(T->left)
     T=T->left;
  } else {
  while(T->right)
    T=T->right;
  }
 }
 return T;
}
Title: Re: bst2dll
Post by birbal on Jul 27th, 2010, 2:56am

on 07/27/10 at 00:54:30, Grimbal wrote:
You are right.  Inexorable's convLnLst doesn't return the right node.  (As a matter of fact, my code has the same problem...).

My mind was so blocked by Inexorable's code that i didn't look at yours :P


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board