CareerCup

Didn't quite understand rahul's idea.

Inorder traversal of a BST is in increasing order, so we can do a inorder, while finding the min in reverse order then swap them:

function main:
	previousNode = null
	InOrderTraversal(root)
----------------------------------------------
function InOrderTraversal(node):
	if node is null then return
	InOrderTraversal(left)

	swap(this, findMinAfterPrevious())
	previousNode = this

	InOrderTraversal(right)
-----------------------------------------------------
function node findMinAfterPrevious():
	reverseTraversal(root, Interger.MAX, null)
----------------------------------------------------
function int reverseTraversal(node, min, minNode):
	if node is null then return
	// if we reach previousNode in this traversal, it means all nodes left to this node is sorted
	if node = previousNode then return
	reverseTraversal(right)

	if node.value < min	
		min = node.value
		minNode = node

	reverseTraversal(left)

I came up with

Consider a BT as an array and apply selection sort.

I will do inorder traversal and while accessing particular node i will call

Inorder_min fxn..

Inorder_min fxn will search the min value from the tree and i will swap it with current index/node.

Now when we encounter the second node then again same fxn will be called and now it will return the secind minimum value and then i will swap these two value and so on..
0(n^2).

Any thoughts on my approach?And any better sol?

Approach could be to pop the element of binary tree in post order traversal so that to have leaf nodes first , and insert it in BST maintaining the property.

Guys my idea is same as game boy..do inorder Traversal..n when we access particular node then at that time find the minimum from the tree and swap these two...same as selction sort

We may need to change every node's data but we can not change the tree's shape, so my idea is:
(1)Inorder traverse the tree and save every node's data and pointers into two arrays. Here we do inorder traverse is because BST's inorder traversal is an sorted sequence.
(2)Sort the data array.
(3)Assign data array's elements to pointer array's data fields.
Time: O(Nlog(N))
Space: O(N)

I have an approach.

Given binary tree with root node *rootBin;

1. Traverse the given binary tree by any traversal methods and push the node value to a linked list. Make sure that the nodes are pushed in sorted manner.

2. Now we have a linked list in sorted order

3. Now write a function binaryToBST which takes actual pointer to root node of binary tree.
Traverse the tree in in order traversal format. similary get the sorted values from list one by one.

binaryToBST(rootNode->left);
rootNode->data = (*head)->value; // value is from linked list
*head = (*head)->next;
binaryToBST(rootNode->right);

I didnt write the entire code. I will update the code once I write and test it.

i) convert Binary tree into array
ii) sort it
iii) using inorder traversal place the numbers it won't change the form of tree

#define MAX 6                //max size of the Binary tree

int compare(const void *a,const void *b){     //for quiksort
    return *(int*)a-*(int*)b;
}

struct node{
    int x;
    node* right;
    node* left;
};

/*   just creating Binary tree out of an array  */

node* convert(int a[],int i){
    if(i-1<MAX){
        node *root=(node*)malloc(sizeof(node));
        if(root==NULL)
            return NULL;
        root->x=a[i-1];
        root->left=convert(a,i*2);
        root->right=convert(a,i*2+1);
        return root;
    }
    return NULL;
}

/*  through inorder traversal place the sorted form of array  */

void inorder(node*root,int a[],int &i){
    if(root!=NULL){
        inorder(root->left,a,i);
        root->x=a[i++];
        inorder(root->right,a,i);
    }
}

/* using queue to print level by level for finding the difference between binary tree and BST */

void q(node* root){
    node* a[MAX+1];
    int f=0,r=0;
    a[r++]=root;
    while(r!=f){
        printf("%d ",a[f++]->x);
        if(a[f-1]->left)
                a[r++]=a[f-1]->left;
        if(a[f-1]->right)
                a[r++]=a[f-1]->right;
    }
}

int main() {
    int a[]={5,6,7,2,1,4},i=0;
    printf("in BS form:\n");
    while(i<MAX)
        printf("%d ",a[i++]);
    i=0;
    node *root=convert(a,1);
    qsort(a,MAX,sizeof(a[0]),compare);
    inorder(root,a,i);
    printf("\nin BST form:\n");
    q(root);
    return 0;

}

Run quicksort on it, but instead iterating over an array do inorder iteration over the tree (the second pointer should iterate 'inorder backwards').
Complexity:
- selectiong comparison key O(1) - take root for example
- iterate to next\prev - O(1) - assuming nodes have pointer to parent. Otherwise it would not be possible to traverse the tree at all in constant memory
- swap O(1)
So the complexity is the same is for regular qsort - asymptotic O(n log n), pessimistic O(n^2) in const memory (in-place)

maybe we should use rotation mechanism to do this?

1. Make a tree clone of BT in respect to the structure.
2. New tree will store no. of node present in left and right subtree.
3. Now change BT to Double Link List.
4. Sort DLL .
5. construct BST using data of New constructed tree.

space O(n), time O(n)