@Surender: it works. check it again using a sample case.
i am first generating inplace BST for left and right subtrees.
Now on this BSt i call the max node or min node function.
Yes you are right, after the swap with root it will cause
inconsistencies again.
that is why the who recursion process is repeated after a swap.
i.e. after u swap a node of left tree using min with the root, you
call the binarytreetoBST(root->left) again from top to down.
heres the way it works for each side of the tree left and right.
first it creates bst for left and right, calls min and max, swaps
value with root if required.
Now root has the final value, no more changes required.
now we call bttoBST(root->left) again if swap took place with left or
bttoBST(root->right) if swap took place with right.
So, whole process repeats two times.
The second time we get the final fixed values for nodes.
On Jul 18, 11:12 pm, surender sanke <surend...@gmail.com> wrote:
> @Dumanshu.... it also doesn't works, as min node doesn't satisfies bst
> conditions, u swap it but it again creates inconsistencies with its left
> subtree.
>
> void binarytreetobst(btree *root)
> {
> if(root == NULL) return;
> else if(root->left == NULL && root->right == NULL) //base-case tree
> of size 1
> return;
> else
> {
> binarytreetobst(root->left);
> binarytreetobst(root->right);
>
> btree* max = max_tree(root->left);
> if(max && max->data > root->data)
> {
> swap(max->data,root->data)
> binarytreetobst(root);
> return;
> }
> btree* min = min_tree(root->right);
> if(min && min->data < root->data)
> {
> swap(min->data,root->data)
> binarytreetobst(root);
> return;
> }
> }
>
> }
>
> other solutions
> 1.
> if O(n) space is allowed.
> fill array elements with tree elements -> sort array -> create BST
>
> 2.
> create a new BST from scratch while deleting from BT and inserting node into
> BST
>
> surender
>
>
>
> On Mon, Jul 18, 2011 at 10:55 PM, Dumanshu <duman...@gmail.com> wrote:
> > got the code for BT to BST from a site..
>
> > btree* max_tree(btree *root)
> > {
> > if(root == NULL)
> > return root;
> > btree * current = root;
> > while(current->right != NULL)
> > {
> > current = current->right;
> > }
> > return current;
> > }
> > btree * min_tree(btree *root)
> > {
> > if(root == NULL)
> > return root;
> > btree * current = root;
> > while(current->left != NULL)
> > {
> > current = current->left;
> > }
> > return current;
> > }
> > void binarytreetobst(btree *root)
> > {
> > //base-case tree is empty
> > if(root == NULL)
> > return;
> > else if(root->left == NULL && root->right == NULL) //base-case tree
> > of size 1
> > return;
> > else
> > {
> > binarytreetobst(root->left);
> > binarytreetobst(root->right);
>
> > btree* max = max_tree(root->left);
> > if(max && max->data > root->data)
> > {
> > int temp = root->data;
> > root->data = max->data;
> > max->data = temp;
> > binarytreetobst(root->left);
>
> > }
> > btree* min = min_tree(root->right);
> > if(min && min->data < root->data)
> > {
> > int temp = root->data;
> > root->data = min->data;
> > min->data = temp;
> > binarytreetobst(root->right);
> > }
> > }
> > }
>
> > On Jul 18, 7:24 pm, Dumanshu <duman...@gmail.com> wrote:
> > > 1. //BT to BST - function used is to swap values
>
> > > Node* bubbleData(Node *root)
> > > {
> > > if(!root)
> > > return NULL;
> > > if(root->right)
> > > {
> > > if(root->data> root->right->data)
> > > swap(&(root->data),&(root->right->data));
> > > root->right = bubbleData(root->right);}
>
> > > if(root->left)
> > > {
> > > if(root->data < root->left->data)
> > > swap(&(root->data),&(root->left->data));
> > > root->left = bubbleData(root->left);}
>
> > > return bubbleData(root);
>
> > > }
>
> > > any case missing??
>
> > > 3. Do we have to give an algorithm for garbage collection like Mark
> > > sweep algo or Do we have to write a code? if code, plz tell how to
> > > write?
>
> > > On Jul 18, 4:59 pm, Balaji S <balaji.ceg...@gmail.com> wrote:
>
> > > > 1. Convert a binary tree to binary search tree inplace..
> > > > 2. Convert a DLL to a binary search tree that is balanced.
> > > > 3. Implement a C++ garbage collector efficiently
>
> > > > --
> > > > With Regards,
> > > > Balaji.S- Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > 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.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
