JIYIK CN >

A binary tree is a non-linear data structure. It is called a binary tree because each node has at most two children. These children are called left and right children. It can also be interpreted as an undirected graph where the topmost node is called the root. A binary search tree (BST) is a type of binary tree with a special property that helps in keeping the data organized in a sorted manner.

In this article, we will discuss how to convert a binary tree to a binary search tree while maintaining the original structure of the binary tree.

Algorithm to convert a binary tree into a binary search tree

• Create an arrarray named to store the in-order traversal of the binary tree nodes.
• arrSort using any sorting algorithm (merge sort O(nlogn), quick sort O(n^2), insertion sort O(n^2) etc.) .
• Traverse the tree in order again and arrstore the elements in the sorted array in a binary tree to obtain a BST.

Converting a binary tree to a BST

• We 4call an in-order traversal on the root node . Recursively traverse left to reach the node 1, which is the leftmost node, and include it in our output; since it is the root node and has no left node, we backtrack to the node 2and include it in our traversal. In this way, we traverse the entire tree and store the results of the in-order traversal [1，2，3，5，4，6]in the array arras .
• arrSort the array using any sorting algorithm to obtain [1，2，3，4，5，6].
• We call in-order traversal again, store the sorted array arrback into the binary tree, and get our BST.

Implementation of converting binary tree to binary search tree

#include <bits/stdc++.h>
using namespace std;

class Node {
    public:
        int data;
        Node *left, *right;
        Node(int x) {
            this->data = x;
            this->left = this->right = NULL;
        }
};
vector<int>v;

void inorder(Node *root) {
    if (root != NULL)
    {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

void storetree(Node*root, int i = 0) {
    if (!root) {
        return;
    }
    storetree(root->left);
    v.push_back(root->data);
    storetree(root->right);
}

void restoretree(Node*root, int& i) {
    if (!root) {
        return;
    }
    restoretree(root->left, i);
    root->data = v[i];
    i++;
    restoretree(root->right, i);
}

void converttoBST(Node*root) {
    if (!root) {
        return;
    }
    storetree(root);
    sort(v.begin(), v.end());
    int i = 0;
    restoretree(root, i);
}

int main() {
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(7);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->right = new Node(2);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    root->right->right->left = new Node(8);
    cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl;
    converttoBST(root);
    cout << "The inorder traversal of the tree is : "; inorder(root); cout << endl;
}

Complexity of the algorithm to convert a binary tree to a BST

Time Complexity

• Average situation

We store the array in sortedand sortedstore the array back into the binary tree with an unordered traversal time complexity of O(n). However, the complexity of sorting the array is O(nlogn), so the total complexity is given as O(nlogn)+2*O(n). The time complexity is O(nlogn).

• Best Case

The time complexity in the best case is O(n). When the given binary tree is already a BST, we do an out-of-order traversal to implement it, and no sorting operation is required.

• Worst case scenario

The worst case time complexity is O(nlogn).

Space complexity

Due to the additional space required for the recursive calls, the space complexity of this algorithm is O(n).