If you mean to convert the binary tree to binary search tree directly , then
BinarytoBST(Node* root)
{
if( root == nulll) return;
BinarytoBST(root->left);
BinarytoBST(root->right);
if( root->left )
Node* NodeL = MAX(root->left);
if ( root->right )
Node* NodeR = MIN(root->right);
if( NodeL->Data > root->data)
{
// swap values.
temp = NodeL->data;
NodeL->data = root->data;
root->data = temp;
BinarytoBST(NodeL);
}
if( NodeR->Data <= root->data)
{
// swap values.
temp = NodeR->data;
NodeR->data = root->data;
root->data = temp;
BinarytoBST(NodeR);
}
--------------------------------------------------------
On Thu, Apr 29, 2010 at 11:23 AM, Algoose Chase <[email protected]>wrote:
> Hi,
>
> How do you define "without extra space" ?
> Doing any order traversal either using recursion or using iteration is
> going to take extra space .
>
> If you are given a binary tree represented by pointers that points to
> children nodes is it possible to do a heap sort without an array ?
>
>
> On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar <[email protected]>wrote:
>
>> my choice is build a min heap .sort the array with heap sort.then find
>> the median of the sorted array and build tree....
>>
>>
>> On Wed, Apr 28, 2010 at 10:16 PM, Vivek S <[email protected]>wrote:
>>
>>> @Rajesh Patidar
>>>
>>> I think we should do in Post order traversal alone. If we go by
>>> Preorder/Inorder we might lose track of children node that is currently
>>> being inserted into the BST. - correct me if im wrong :)
>>>
>>>
>>> On 28 April 2010 15:30, Rajesh Patidar <[email protected]> wrote:
>>>
>>>> pickup node in any order no matter(pre,post,inorder) and just one by
>>>> one. start adding the node into bst no need to use extra space u have
>>>> to just ditach the node from binary tree and attach it in bst.
>>>>
>>>> On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra <[email protected]>
>>>> wrote:
>>>> > How to build BST from binary tree in place i.e without extra space ??
>>>> >
>>>> > --
>>>> > 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]<algogeeks%[email protected]>
>>>> .
>>>> > For more options, visit this group at
>>>> > http://groups.google.com/group/algogeeks?hl=en.
>>>> >
>>>>
>>>>
>>>>
>>>> --
>>>> ~~~~BL/\CK_D!AMOND~~~~~~~~
>>>>
>>>> --
>>>> 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]<algogeeks%[email protected]>
>>>> .
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>>
>>>
>>>
>>> --
>>> "Reduce, Reuse and Recycle"
>>> Regards,
>>> Vivek.S
>>>
>>> --
>>> 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]<algogeeks%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> yezhu malai vaasa venkataramana Govinda Govinda
>>
>> --
>> 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]<algogeeks%[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.
