wu :: forums - Print Page


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

        riddles >> cs >> correcting a BST
        
(Message started by: inexorable on Jan 27^th, 2007, 11:20pm)

Title: correcting a BST
Post by inexorable on Jan 27^th, 2007, 11:20pm

One of the leaves of the binary search tree is connected to some other node of the binary search tree by mistake. So disconnect the wrong connection assuming the wrong connection is at a higher depth than the correct connection.
So write a function which corrects the given binary tree.

PS:- I heard that this was an interview question. As the question does not seem well defined, please make any necessary assumptions.

Thanks.

Title: Re: correcting a BST
Post by sk on Jan 28^th, 2007, 4:38pm

it shud be straight forward. u can do it in 3 steps

1) find the node

use a BFT and at every node check if the BST property holds leftchild <= parent node <= rightchild. If not then
faultyNode is the left or right kid not satisfying the eq.

2) delete the node (since this is the leaf node there is no readjustment that is to be made)

make parent-><faulty kid> = null;

3. Insert it again
insert it in proper place.

however, this would get interesting if the faulty one was an internal node. Try it for that.