Author |
Topic: bst2dll (Read 5915 times) |
|
ic10503
Junior Member
Gender: 
Posts: 57
|
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
|
|
 IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
 |
Re: bst2dll
« Reply #1 on: Jul 31st, 2008, 4:23am » |
 Quote  Modify
|
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
|
|
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: bst2dll
« Reply #2 on: Jul 31st, 2008, 4:47am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
ic10503
Junior Member
Gender:
Posts: 57
|
|
Re: bst2dll
« Reply #3 on: Jul 31st, 2008, 5:35am » |
Quote Modify
|
on Jul 31st, 2008, 4:47am, 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
|
|
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: bst2dll
« Reply #4 on: Aug 1st, 2008, 12:23am » |
Quote Modify
|
on Jul 31st, 2008, 5:35am, 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.
|
|
IP Logged |
|
|
|
gt
Newbie
Posts: 13
|
|
Re: bst2dll
« Reply #5 on: Jul 4th, 2009, 2:16am » |
Quote Modify
|
can this be done without using any auxiliary data structure...like without using any recursion or a user stack.....
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: bst2dll
« Reply #6 on: Jul 4th, 2009, 2:32am » |
Quote Modify
|
on Jul 4th, 2009, 2:16am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ONS
Newbie
Gender:
Posts: 41
|
|
Re: bst2dll
« Reply #7 on: Jul 8th, 2009, 12:13am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: bst2dll
« Reply #8 on: Jul 8th, 2009, 1:07am » |
Quote Modify
|
on Jul 8th, 2009, 12:13am, 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
|
| « Last Edit: Jul 8th, 2009, 1:07am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
alphare
Newbie
Posts: 8
|
|
Re: bst2dll
« Reply #9 on: Oct 14th, 2009, 2:56pm » |
Quote Modify
|
ic10503, nks,
Both of your solutions are not correct.
Anyone think it can be done in O(1) space>
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: bst2dll
« Reply #10 on: Oct 14th, 2009, 3:08pm » |
Quote Modify
|
on Oct 14th, 2009, 2:56pm, 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.
|
| « Last Edit: Oct 14th, 2009, 3:09pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: bst2dll
« Reply #11 on: Oct 15th, 2009, 3:16pm » |
Quote Modify
|
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
|
| « Last Edit: Oct 16th, 2009, 11:51am by Grimbal » |
IP Logged |
|
|
|
alphare
Newbie
Posts: 8
|
|
Re: bst2dll
« Reply #12 on: Oct 15th, 2009, 11:38pm » |
Quote Modify
|
this one is incorrect either...
on Oct 15th, 2009, 3:16pm, 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;
}
|
|
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: bst2dll
« Reply #13 on: Oct 16th, 2009, 12:50am » |
Quote Modify
|
You know, unless you say why they are supposedly incorrect, it's not a very convincing statement.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
alphare
Newbie
Posts: 8
|
|
Re: bst2dll
« Reply #14 on: Oct 16th, 2009, 1:25am » |
Quote Modify
|
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 Oct 16th, 2009, 12:50am, towr wrote:| You know, unless you say why they are supposedly incorrect, it's not a very convincing statement. |
|
|
| « Last Edit: Oct 16th, 2009, 10:04am by alphare » |
IP Logged |
|
|
|
alphare
Newbie
Posts: 8
|
|
Re: bst2dll
« Reply #15 on: Oct 16th, 2009, 1:29am » |
Quote Modify
|
OK, traverse the link list of Grimbal again and fix the prev problem do yield a solution that is O(1) space. 
on Oct 16th, 2009, 12:50am, towr wrote:| You know, unless you say why they are supposedly incorrect, it's not a very convincing statement. |
|
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: bst2dll
« Reply #16 on: Oct 16th, 2009, 11:52am » |
Quote Modify
|
on Oct 15th, 2009, 11:38pm, alphare wrote:| this one is incorrect either... |
|
Oops... right. Code fixed. I hope.
|
|
IP Logged |
|
|
|
alphare
Newbie
Posts: 8
|
|
Re: bst2dll
« Reply #17 on: Oct 16th, 2009, 12:04pm » |
Quote Modify
|
Yeah, It works fine. Cheers... 
on Oct 16th, 2009, 11:52am, Grimbal wrote:
Oops... right. Code fixed. I hope. |
|
|
|
IP Logged |
|
|
|
Lol
Newbie
Gender:
Posts: 13
|
|
Re: bst2dll
« Reply #18 on: Dec 2nd, 2009, 6:23am » |
Quote Modify
|
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....... 
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: bst2dll
« Reply #19 on: Dec 3rd, 2009, 1:39am » |
Quote Modify
|
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;
}
|
| « Last Edit: Dec 3rd, 2009, 1:40am by nks » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: bst2dll
« Reply #20 on: Jan 12th, 2010, 11:04pm » |
Quote Modify
|
on Jul 31st, 2008, 4:47am, 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
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: bst2dll
« Reply #21 on: Apr 10th, 2010, 11:36am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: bst2dll
« Reply #22 on: Apr 22nd, 2010, 12:28am » |
Quote Modify
|
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.. 
|
| « Last Edit: Apr 22nd, 2010, 12:29am by AB » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: bst2dll
« Reply #23 on: May 31st, 2010, 2:47am » |
Quote Modify
|
on Apr 22nd, 2010, 12:28am, 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.. |
|
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
|
| « Last Edit: May 31st, 2010, 2:48am by birbal » |
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: bst2dll
« Reply #24 on: Jul 24th, 2010, 11:48pm » |
Quote Modify
|
on Apr 10th, 2010, 11:36am, 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
|
| « Last Edit: Jul 24th, 2010, 11:49pm by birbal » |
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print