@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
