Update appNew update is available. Click here to update.

Converting Binary Tree to Binary Search Tree

Kanak Rana
Last Updated: Jan 25, 2023
MEDIUM

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.

Converting Binary Tree to Binary Search 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.

Binary Tree (Pre-requisite)

Code Structure:

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


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)
	{ 
		// Working on the current root.
		cout<<root->data<<" "; 
		// Traversing to the left sub tree.
		PreOrder(root->left);
		// Traversing to the right sub tree.
		PreOrder(root->right); 
	}
}
void InOrder(struct Node* root)
{
	// If the root is not null.
	if(root)
	{ 
		// Traversing to the left sub tree.
		InOrder(root->left); 
		// Working on the current root.
		cout<<root->data<<" ";
		// Traversing to the right sub tree.
		InOrder(root->right); 
		
	}
}
void PostOrder(struct Node* root)
{
	
	// If the root is not null.
	if(root)
	{ 
		// Traversing to the left sub tree.
		PostOrder(root->left); 
		// Traversing to the right sub tree.
		PostOrder(root->right); 
		// Working on the current root.
		cout<<root->data<<" "; 
	}
}


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.

Binary Search Tree (BST)

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?

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:

Binary Search Tree (BST)

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

// Sorted InOrderArray
0 1 2 3 4
// Tree before conversion 
1 2 3 4 0 
// Tree after conversion
0 1 2 3 4 


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

How do you convert a binary tree to a binary search tree in Java?

To convert a binary tree to a binary search tree, you need to first create an array that will store the inorder traversal of a tree, then you need to sort the array, do an inorder traversal of a tree again and finally copy the elements to the tree nodes.

How can we convert a binary tree into a 2 tree?

If we replace each empty subtree by a new external node, a binary tree will be converted into a 2 tree.

What is the first step in converting a general tree to a binary tree?

First you have to insert an edge that connects all the siblings of the general tree.

Is a binary search tree a complete binary tree?

A complete binary tree is a tree in which all levels are filled except the lowest one. If a binary search tree fulfils this rule, then it becomes a complete binary tree.

Conclusion

This article was an insight into Converting Binary Tree to Binary Search Tree. we discussed about the binary tree and binary search tree very deeply and through code with proper explanation and time complexity.

Gear up your placement preparation by solving daily DSA problems. You can also refer to guided paths for learning about competitive programming. Read about hot topics such as big datadeep learningcomputer vision, and many more. 

Happy Learning!

Was this article helpful ?
0 upvotes