Author |
Topic: Nodes Of BST exchanged (Read 7461 times) |
|
TrozanHrorse
Newbie
Gender: 
Posts: 4
|
 |
Nodes Of BST exchanged
« on: Feb 5th, 2009, 8:27am » |
 Quote  Modify
|
I heard an interview question which goes as follows:
Two nodes of the BST are exchanged , and a root pointer is given. We have to correct the BST........ hw this is to be done
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Nodes Of BST exchanged
« Reply #1 on: Feb 8th, 2009, 2:56pm » |
Quote Modify
|
I'd start with a depth first traversal, and check whether the child nodes are in the right place for it to be a BST. If all the elements are unique, there shouldn't be a problem finding them in this way. And if one of the nodes isn't the ancestor of the other, then you'll find both. And then you just switch the pointers in the parent nodes.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Nodes Of BST exchanged
« Reply #2 on: Apr 10th, 2009, 4:06pm » |
Quote Modify
|
on Feb 8th, 2009, 2:56pm, towr wrote:| I'd start with a depth first traversal, and check whether the child nodes are in the right place for it to be a BST. If all the elements are unique, there shouldn't be a problem finding them in this way. And if one of the nodes isn't the ancestor of the other, then you'll find both. And then you just switch the pointers in the parent nodes. |
|
Nodes are exchanged or two nodes' values are exchanged
if it is the latter, then switching the pointers will change the BST.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Nodes Of BST exchanged
« Reply #3 on: Apr 11th, 2009, 3:39am » |
Quote Modify
|
on Apr 10th, 2009, 4:06pm, R wrote:Nodes are exchanged or two nodes' values are exchanged
if it is the latter, then switching the pointers will change the BST. |
|
Well, the problem says the nodes are exchanged, rather than their values.
Otherwise you need to find both values that are out of place and switch them.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Nodes Of BST exchanged
« Reply #4 on: Apr 11th, 2009, 4:34am » |
Quote Modify
|
on Apr 11th, 2009, 3:39am, towr wrote:
Well, the problem says the nodes are exchanged, rather than their values.
Otherwise you need to find both values that are out of place and switch them.
|
|
so just two nodes are exchanged... their subtree (descendents) are not
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Nodes Of BST exchanged
« Reply #5 on: Apr 11th, 2009, 4:38am » |
Quote Modify
|
on Apr 11th, 2009, 4:34am, R wrote:| so just two nodes are exchanged... their subtree (descendents) are not |
|
I'd imagine they stay connected to the nodes they are connected to before the switch. So if you switch the nodes, you switch the subtrees.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Nodes Of BST exchanged
« Reply #6 on: Apr 12th, 2009, 7:06pm » |
Quote Modify
|
on Apr 11th, 2009, 4:38am, towr wrote:
I'd imagine they stay connected to the nodes they are connected to before the switch. So if you switch the nodes, you switch the subtrees. |
|
well then those two nodes can't have a ancestor-descendant relationship. As one will be in the subtree of other. Moving the ancestor will move the descendant too.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
TrozanHrorse
Newbie
Gender:
Posts: 4
|
|
Re: Nodes Of BST exchanged
« Reply #7 on: Apr 12th, 2009, 10:23pm » |
Quote Modify
|
Don't know the exact language of the question as I have only heard of it(most probably the question is exchange of values of the nodes)...But let's discuss the solution to both of these question.....
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
on Apr 12th, 2009, 7:06pm, R wrote:
well then those two nodes can't have a ancestor-descendant relationship. As one will be in the subtree of other. Moving the ancestor will move the descendant too. |
|
Why should that be a hurdle? You're exchanging two pointer values, that can always be done. You may not have a tree afterwards, but that's someone else's problem.
Of course, as it turns out, if one of the exchanged nodes is originally the parent of the other, you won't find any problem in the BST, since the problem is disconnected from it.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Nodes Of BST exchanged
« Reply #9 on: Apr 13th, 2009, 7:07am » |
Quote Modify
|
on Apr 13th, 2009, 1:11am, towr wrote:
Why should that be a hurdle? You're exchanging two pointer values, that can always be done. You may not have a tree afterwards, but that's someone else's problem.
Of course, as it turns out, if one of the exchanged nodes is originally the parent of the other, you won't find any problem in the BST, since the problem is disconnected from it.
|
|
Yes ofcourse two poitners can be exchanged. I was talking in the context of this problem. I meant, if that is the case, then we won't be able to solve the problem(correct the BST).
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Nodes Of BST exchanged
« Reply #10 on: Apr 13th, 2009, 7:14am » |
Quote Modify
|
on Apr 12th, 2009, 10:23pm, TrozanHrorse wrote:Don't know the exact language of the question as I have only heard of it(most probably the question is exchange of values of the nodes)...But let's discuss the solution to both of these question.....
|
|
Well in case of exchanged-values, we will do an in-order traversal and see which nodes are out of order, and will remember their address. At the end just swap their contents.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
TrozanHrorse
Newbie
Gender:
Posts: 4
|
|
Re: Nodes Of BST exchanged
« Reply #11 on: Apr 13th, 2009, 7:20am » |
Quote Modify
|
It will not be easy to do that as there will be many cases and moreover if any how we do it by that method that will not be an efficient approach
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Nodes Of BST exchanged
« Reply #12 on: Apr 13th, 2009, 7:50am » |
Quote Modify
|
on Apr 13th, 2009, 7:07am, R wrote:| I meant, if that is the case, then we won't be able to solve the problem(correct the BST). |
|
Well, that's true, but it happens. You can't always fix things in life 
on Apr 13th, 2009, 7:20am, TrozanHrorse wrote:| It will not be easy to do that as there will be many cases and moreover if any how we do it by that method that will not be an efficient approach |
|
Why would it be a problem? You just need to detect whether the next node in the traversal is smaller than the previous one. Either there will be one or two places where the sequence doesn't increase monotonically. Switch the value before the first 'break' with the one after the last 'break'.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Nodes Of BST exchanged
« Reply #13 on: Apr 13th, 2009, 10:14am » |
Quote Modify
|
on Apr 13th, 2009, 7:20am, TrozanHrorse wrote:| It will not be easy to do that as there will be many cases and moreover if any how we do it by that method that will not be an efficient approach |
|
on Apr 13th, 2009, 7:20am, TrozanHrorse wrote:| It will not be easy to do that as there will be many cases and moreover if any how we do it by that method that will not be an efficient approach |
|
This will work...
Code:
void inorder(node *root)
{
if(root == NULL) return;
//varibales for storing last visited node information = = initialized carefully
static int prev_val = get_minimum(); //get_minimum() returns the minimum value of BST
static node* prev_addr = NULL;
inorder(root->left);
//at node root
if(root->data < prev_val)
{
if(node1 == NULL) //first out-of-order node found
node1 = prev_addr;
node2 = root; //always
}
//update last visited node information
prev_val = root->data;
prev_addr = root;
inorder(root->right);
}
|
|
Swap(node1->data, node2->data);
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Nodes Of BST exchanged
« Reply #14 on: Apr 13th, 2009, 4:59pm » |
Quote Modify
|
For the case: when the nodes are exchanged (along with their subtrees) not only values, the following approach will work. Time O(n).
Assuming that the exchanged nodes were not related by ancestor-descendant relationship.
Code:
enum {LEFT, RIGHT};
void postorder(node *root)
{
static int i = 0;
if(i == 2) //both nodes found => no need to explore further
return;
if(root != NULL)
{
postorder(root->left);
postorder(root->right);
// at node root check BST property
if(root->left != NULL)
{
if(root->data < root->left->data) //violation of BST property
{ exch_node[i].addr = root; exch_node[i].child = LEFT; i++;}
}
if(root->right != NULL)
{
if(root->data > root->right->data) //violation of BST property
{ exch_node[i].addr = root; exch_node[i].child = RIGHT; i++}
}
}
}
|
|
swap addresses exch_node[0] and exch_node[1].
somthing like
Code:
swap( (exch_node[0]->left * (exch_node[0].child == LEFT) + exch_node[0]-> right *(exch_node[0].child == RIGHT)),
(exch_node[1]->left * (exch_node[1].child == LEFT) + exch_node[1]-> right *(exch_node[1].child == RIGHT)) );
|
|
will work.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
TrozanHrorse
Newbie
Gender:
Posts: 4
|
|
Re: Nodes Of BST exchanged
« Reply #15 on: Apr 14th, 2009, 3:05am » |
Quote Modify
|
Thanx R for the code my problem is solved .....and thanx everybody for your responses 
|
|
IP Logged |
|
|
|
__Debug
Guest
|
|
Re: Nodes Of BST exchanged
« Reply #16 on: Jul 23rd, 2009, 8:50pm » |
Quote Modify
 Remove
|
i think we do not need to search for both the nodes. Once first 'bad' node is found using inorder traversal (or by using the valid BST property as R suggested) , just look for the right position of that node using binary search. There we can find the second 'bad' node (as bad nodes are merely exchanged) . exchange the two
|
| « Last Edit: Jul 23rd, 2009, 8:52pm by __Debug » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print