Convert Binary Tree to Binary Search Tree
 Algorithm of Converting Binary Tree to BST
 Convert Binary Tree to BST Illustration
 Convert Binary Tree to BST Implementation
 Convert Binary Tree to BST Algorithm Complexity
A Binary Tree is a nonlinear 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

We call inorder traversal on root node
4
. Recursively traverse left to reach node1
, which is the leftmost node, and include it in our output; as it is the root and has no left node, we traceback to node2
and include it in our traversal. In this way, we traverse the whole tree and store the inorder traversal in the arrayarr
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 bestcase 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 worstcase 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.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Insertion
 Linked List Merge Sort
Related Article  Binary Tree
 Binary Search Tree Check
 Binary Search Tree Inorder Succesor
 Binary Tree Traversal
 Binary Search Tree
 Binary Search Tree Delete