Binary Tree to Binary Search Tree Conversion | GeeksforGeeks

Binary Tree to Binary Search Tree Conversion | GeeksforGeeks
Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.
1) Create a temp array arr[] that stores inorder traversal of the tree. This step takes O(n) time.
2) Sort the temp array arr[]. Time complexity of this step depends upon the sorting algorithm. In the following implementation.
3) Again do inorder traversal of tree and copy array elements to tree nodes one by one. This step takes O(n) time.

oid arrayToBST (int *arr, struct node* root, int *index_ptr)

{

    // Base Case

    if (root == NULL)

      return;

    /* first update the left subtree */

    arrayToBST (arr, root->left, index_ptr);

    /* Now update root's data and increment index */

    root->data = arr[*index_ptr];

    (*index_ptr)++;

    /* finally update the right subtree */

    arrayToBST (arr, root->right, index_ptr);

}

void binaryTreeToBST (struct node *root)

{

    // base case: tree is empty

    if(root == NULL)

       return;

    /* Count the number of nodes in Binary Tree so that

       we know the size of temporary array to be created */

    int n = countNodes (root);

    // Create a temp array arr[] and store inorder traversal of tree in arr[]

    int *arr = new int[n];

    int i = 0;

    storeInorder (root, arr, &i);

    // Sort the array using library function for quick sort

    qsort (arr, n, sizeof(arr[0]), compare);

    // Copy array elements back to Binary Tree

    i = 0;

    arrayToBST (arr, root, &i);

    // delete dynamically allocated memory to avoid meory leak

    delete [] arr;

}

Read full article from Binary Tree to Binary Search Tree Conversion | GeeksforGeeks