Converting Binary Tree to Binary Search Tree

Introduction

Most of the time in programming we tend to have a real-world data structure to implement business logic and functions. One of the most prevailing data structures for this purpose is called a Tree.

In basic data structures, we have learned about linked lists, stacks, queues, etc. consisting of nodes (element container). Most of the time these nodes are connected in a linear fashion but in Trees, we shape this structure in a non-linear fashion. In Trees, the nodes are with zero or one or more than one node. Such trees are called n-array trees. Although in this article we will be discussing Binary Trees i.e. trees having at most two child nodes. 

Binary Tree (Pre-requisite)

A Binary Tree is a Data Structure having a root node and at most two children nodes. Each of these children forms the left subtree and the right subtree. The end nodes or the leaf nodes have no children and are pointed by a NULL pointer.

Code Structure:

struct node{
	int data;
	node *left;  // pointer to left subtree
	node *right; // pointer to right sub tree
};

Now we can see that in this Binary tree the data present in the nodes have no particular order of constraints. So we can traverse it recursively in three ways, namely:

• Preorder Traversal: Visit the current node, visit the left sub tree, visit the right sub tree.
• InOrder Traversal: Visit the left sub tree, visit the current node, visit the right sub tree.
• PostOrder Traversal: Visit the left sub tree, visit the right sub tree, visit the current node.

Well let us look at their code implementations too:

struct node{
	int data;
	node *left;
	node *right;
};
void PreOrder(struct Node* root){
	//if the root is not null
	if(root){ 
		cout<<root->data<<" "; // working on the current root
		PreOrder(root->left); // traversing to the left sub tree
		PreOrder(root->right); // traversing to the right sub tree
	}
}
void InOrder(struct Node* root){
	//if the root is not null
	if(root){ 
		InOrder(root->left); // traversing to the left sub tree
		cout<<root->data<<" "; // working on the current root
		InOrder(root->right); // traversing to the right sub tree
	}
}
void PostOrder(struct Node* root){
	//if the root is not null
	if(root){ 
		PostOrder(root->left); // traversing to the left sub tree
		PostOrder(root->right); // traversing to the right sub tree
		cout<<root->data<<" "; // working on the current root
	}
}

Now when we know that these traversals result in an array of ordered elements in which we encounter them in the current traversal structures. From any two of these, the original tree can be generated. If we consider only PreOrder and PostOrder traversal list then we can have more than one binary trees. But if we consider InOrder & PreOrder or InOrder & PostOrder then we can have a unique BT from these set of traversals.

Well, what will happen if we have some order in the insertion and creation of this BT? Let us look at such an implementation known as Binary Search Trees which come very handy in various time complexity reducing programs.

Exciting Scholarship Programme by Coding Ninjas to upskill this summer

Binary Search Tree (BST)

In the above diagram let’s consider the node 4(root), left node of the root is 2 which is smaller than 4 and all the nodes in the left subtree {1,2,3} are smaller than 4, whereas in the right subtree {5,6} are the nodes greater than 4 along with left and right subtrees are Binary Search Trees and hence the above tree satisfies to be a Binary Search Tree.

Now we will discuss the most interesting property of this tree. Let us have a InOrder traversal of the above tree –

The result of the InOrder array list gives – {1,2,3,4,5,6}, found something interesting? Yes, the array list is sorted. Whenever we do an InOrder traversal of a Binary Search Tree we always get a sorted list. This property will be used in the conversion of BT to Binary Search Tree.

Well first we need to check if the given BT is already a BST or not. How we do that?

 We have launched a new Preparation Guide for your next interview.

Code Implementation:

#include <bits/stdc++.h>
using namespace std;
struct node{
	int data;
	struct node *left;
	struct node *right;
};
struct node* newNode(int val){
	struct node *newnode = new node();
	newnode->data = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
bool checkBST(node *root,node *l,node *r){
	if(root == NULL)return true;
	if(l && root->data <= l->data)
		return false;
	if(r && root->data >= r->data)
		return false;
	return checkBST(root->left,l,root) && checkBST(root->right,root,r);
}
void travel(struct node *root){
	if(root){
		cout<<root->data<<" ";
		travel(root->left);
		travel(root->right);
	}
}
int main() {
	// your code goes here
	struct node *root = newNode(4);
	root->left = newNode(2);
	root->right = newNode(5);
	root->left->right = newNode(3);
	root->left->left = newNode(1);
	travel(root);
	cout<<checkBST(root);
	return 0;
}

Now when we have checked that the given tree is not BST then only, we will move forward to conversion.

Let us consider an input on which we will work:

Conversion from Binary Tree to Binary Search Tree

Algorithm:

• Find the InOrder traversal of the given BT. This will result in an array of elements. Let the array be denoted as InOrderArray.
• Sort the InOrder Array. (InOrder traversal of Binary Search Tree gives a sorted array)
• Pick one element from the InOrder array and traverse(InOrder) from the root of the BT given.
• If the current element is not NULL and is different from the InOrderArray element then replace the element in the Binary Tree.
• Traverse the whole array and tree and do the above steps for the complete tree and array.

InOrder property of Binary Search Tree is used in the algorithm.

Code Implementation:

#include <bits/stdc++.h>
using namespace std;
struct node{
	int data;
	struct node *left;
	struct node *right;
};
struct node* newNode(int val){
	struct node *newnode = new node();
	newnode->data = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
bool checkBST(node *root,node *l,node *r){
	if(root == NULL)return true;
	if(l && root->data <= l->data)
		return false;
	if(r && root->data >= r->data)
		return false;
	return checkBST(root->left,l,root) && checkBST(root->right,root,r);
}
void convertBST(node *root,vector<int> InOrderArray,int& i){
	if(root){
		convertBST(root->left,InOrderArray,i);
		root->data = InOrderArray[i++];
		convertBST(root->right,InOrderArray,i);
	}
}
void InOrder(struct node *root,vector<int>& v){
	if(root){
		//cout<<root->data<<" ";
		InOrder(root->left,v);
		v.push_back(root->data); //inorder
		InOrder(root->right,v);
	}
}
void travel(node *root){
	if(root){
		travel(root->left);
		cout<<root->data<<" ";
		travel(root->right);
	}
}
int main() {
	// your code goes here
	struct node *root = newNode(4);
	root->left = newNode(2);
	root->right = newNode(0);
	root->left->right = newNode(3);
	root->left->left = newNode(1);
	//travel(root);
	//cout<<checkBST(root,NULL,NULL);
//Check this condition before moving forward
//I have considered that the tree is not given in BST
	vector<int> arr;
	InOrder(root,arr);
	int n = arr.size();
	sort(arr.begin(),arr.end());
	for(auto e : arr)cout<<e<<" ";
	cout<<endl;
	travel(root);
	cout<<endl;
	int i = 0;
	convertBST(root,arr,i);
	travel(root);
	return 0;
}
 

Output of the above result is –
0 1 2 3 4 //sorted InOrderArray
1 2 3 4 0 //Tree before conversion
0 1 2 3 4 //Tree after conversion

Time Complexity: O(nlogn), where n is the number of nodes in the tree. We can see that after conversion the Binary Search Tree InOrder traversal must give a sorted array of elements and this is the case in the output. Hence our program has worked for all the cases.

In this way, we have converted a Binary Tree to a Binary Search Tree with efficient time complexity. Hope this algorithm is useful to aspiring developers and programmers.

Frequently Asked Questions

Found this article useful? Read about Fenwick Tree to get more insights.

By Aniruddha Guin