Author |
Topic: correcting a BST (Read 527 times) |
|
inexorable
Full Member
Posts: 211
|
 |
correcting a BST
« on: Jan 27th, 2007, 11:20pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
sk
Newbie
Posts: 45
|
|
Re: correcting a BST
« Reply #1 on: Jan 28th, 2007, 4:38pm » |
Quote Modify
|
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.
|
| « Last Edit: Jan 28th, 2007, 4:39pm by sk » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print