@shashi: once we have two pointer where anomalies exist, we can exchange
their data value to obtain original BST...
On Wed, Sep 5, 2012 at 12:38 PM, shashi kant shashiski...@gmail.com wrote:
Is it required only to retain the BST property ?? or to retain the
original BST (tree)
*Shashi
that what i mentioned finding original BST or a correcting the BST property
...
my method will only maintains the BST property...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
Is it required only to retain the BST property ?? or to retain the
original BST (tree)
*Shashi Kant *
***Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*
On Tue, Sep 4, 2012 at 1:56 PM,
@Shashi : i dont see any differencebcoz only 2 nodes are swapped
..after correcting it...it shud maintain BST property wich automatically
retain original tree
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
well in that case there can be simpler ways to do it
do an inorder traversal while checking prevcurnext ordering maintained
if not then make it in proper order ,although whole tree has to be
traversed to fix it.
*Shashi Kant *
***Think positive and find fuel in failure*
@Shashi : please check previous discussion on this thread.
On Wed, Sep 5, 2012 at 2:09 PM, shashi kant shashiski...@gmail.com wrote:
well in that case there can be simpler ways to do it
do an inorder traversal while checking prevcurnext ordering maintained
if not then make it in proper order
@atul: correctly caught...
here you have to notice that if u get only one violation not second
violation ill the last... then sure the violation is created because of
swapping of previous and current of first violation...
so when you got first violation and put first marker on previous time put
while doing in-order traversal, we have to check if(prev current) --
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for swapping.
swap both ..
If we don't get the violation for the second time .. means both are
@bharat: +1
i have tried some test cases.. working finely.. @anyone pls verify??
On Mon, Sep 3, 2012 at 11:58 AM, bharat b bagana.bharatku...@gmail.comwrote:
while doing in-order traversal, we have to check if(prev current) --
then mark prev element for swapping in the first time violation..
@rahul : Here are the boundary cases need to be taken care of :-
suppose given BST is the following :-
root=allocate(70);
root-right=allocate(75);
root-left=allocate(50);
root-left-left=allocate(20);
root-left-left-right=allocate(25);
root-left-left-left=allocate(10);
i guess i missed this part of bharat post :-
/*
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
*/
i was saying the same.so it will work.
On 9/4/12, atul anand atul.87fri...@gmail.com wrote:
@rahul : Here are the boundary cases need
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
13 matches
Mail list logo
