wu :: forums - Print Page


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

        riddles >> microsoft >> Nodes Of BST exchanged
        
(Message started by: TrozanHrorse on Feb 5^th, 2009, 8:27am)

Title: Nodes Of BST exchanged
Post by TrozanHrorse on Feb 5^th, 2009, 8:27am

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???

Title: Re: Nodes Of BST exchanged
Post by towr on Feb 8^th, 2009, 2:56pm

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.

Title: Re: Nodes Of BST exchanged
Post by R on Apr 10^th, 2009, 4:06pm

on 02/08/09 at 14:56:30, towr wrote:

Nodes are exchanged or two nodes' values are exchanged???
if it is the latter, then switching the pointers will change the BST.

Title: Re: Nodes Of BST exchanged
Post by towr on Apr 11^th, 2009, 3:39am

on 04/10/09 at 16:06:50, 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.

Title: Re: Nodes Of BST exchanged
Post by R on Apr 11^th, 2009, 4:34am

on 04/11/09 at 03:39:37, 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???

Title: Re: Nodes Of BST exchanged
Post by towr on Apr 11^th, 2009, 4:38am

on 04/11/09 at 04:34:27, 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.

Title: Re: Nodes Of BST exchanged
Post by R on Apr 12^th, 2009, 7:06pm

on 04/11/09 at 04:38:26, 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.

Title: Re: Nodes Of BST exchanged
Post by TrozanHrorse on Apr 12^th, 2009, 10:23pm

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.....

Title: Re: Nodes Of BST exchanged
Post by towr on Apr 13^th, 2009, 1:11am

on 04/12/09 at 19:06:04, 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.

Title: Re: Nodes Of BST exchanged
Post by R on Apr 13^th, 2009, 7:07am

on 04/13/09 at 01:11:51, towr wrote:

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).

Title: Re: Nodes Of BST exchanged
Post by R on Apr 13^th, 2009, 7:14am

on 04/12/09 at 22:23:52, 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.

Title: Re: Nodes Of BST exchanged
Post by TrozanHrorse on Apr 13^th, 2009, 7:20am

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

Title: Re: Nodes Of BST exchanged
Post by towr on Apr 13^th, 2009, 7:50am

on 04/13/09 at 07:07:58, 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 04/13/09 at 07:20:57, 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'.

Title: Re: Nodes Of BST exchanged
Post by R on Apr 13^th, 2009, 10:14am

on 04/13/09 at 07:20:57, 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 04/13/09 at 07:20:57, 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);

Title: Re: Nodes Of BST exchanged
Post by R on Apr 13^th, 2009, 4:59pm

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.

Title: Re: Nodes Of BST exchanged
Post by TrozanHrorse on Apr 14^th, 2009, 3:05am

Thanx R for the code my problem is solved .....and thanx everybody for your responses :)

Title: Re: Nodes Of BST exchanged
Post by __Debug on Jul 23^rd, 2009, 8:50pm

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