Convert Binary Tree to Binary Search Tree

  1. Algorithm of Converting Binary Tree to BST
  2. Convert Binary Tree to BST Illustration
  3. Convert Binary Tree to BST Implementation
  4. Convert Binary Tree to BST Algorithm Complexity

A Binary Tree is a non-linear data structure. It is called a binary tree because each node has a maximum of two children. These children are called left children and right children. It can also be interpreted as an undirected graph in which the topmost node is called root. A Binary Search Tree (BST) is a binary tree with special properties that helps to keep the data organized in a sorted fashion.

In this tutorial, we will discuss how to convert a binary tree to BST while maintaining the Binary Tree’s original structure.

Algorithm of Converting Binary Tree to BST

  • Create an array called arr to store the inorder traversal of binary tree nodes.
  • Sort arr using any sorting algorithm (MergeSort O(nlogn), QuickSort O(n^2), Insertion Sort O(n^2), etc.).
  • Again, do the inorder traversal of the tree and store the elements in the binary tree from the sorted array arr to yield the BST.

Convert Binary Tree to BST Illustration

Binary Tree to BST Illustration

  • We call inorder traversal on root node 4. Recursively traverse left to reach node 1, which is the leftmost node, and include it in our output; as it is the root and has no left node, we traceback to node 2 and include it in our traversal. In this way, we traverse the whole tree and store the inorder traversal in the array arr as [1, 2, 3, 5, 4, 6].
  • Sort the array arr using any sorting algorithm to get [1, 2, 3, 4, 5, 6].
  • We again call the inorder traversal to store the sorted array arr back in the binary tree to get our BST.

Convert Binary Tree to BST Implementation

#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;
}

Convert Binary Tree to BST Algorithm Complexity

Time Complexity

  • Average Case

The time complexity of doing the inorder traversal in which we store the array in sorted and store the sorted array back to the binary tree is O(n). But, the complexity of sorting the array is O(nlogn) and hence the total complexity is given as O(nlogn) + 2*O(n). The time complexity is of the order of O(nlogn).

  • Best Case

The best-case time complexity is of the order of O(n). When the given binary tree is already a BST, we do the inorder traversal to realize it, and no sorting operations are required.

  • Worst Case

The worst-case time complexity is of the order of O(nlogn).

Space Complexity

The algorithm’s space complexity is O(n) due to the extra space required by recursion calls.

Write for us
DelftStack articles are written by software geeks like you. If you also would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Data Structure

  • Circular Doubly Linked List
  • Circular Linked List
  • Doubly Linked List
  • Linked List Deletion
  • Related Article - Binary Tree

  • Circular Doubly Linked List
  • Circular Linked List
  • Doubly Linked List
  • Linked List Deletion
  • Related Article - Binary Search Tree

  • Circular Doubly Linked List
  • Circular Linked List
  • Doubly Linked List
  • Linked List Deletion