Home Â» Technical Interview Questions Â» Tree Interview Questions Â» Binary Tree to Binary Search Tree Conversion

# Binary Tree to Binary Search Tree Conversion

In binary tree to binary search tree conversion problem, we have given a binary tree convert it to Binary Search Tree without changing the structure of the tree.

## Example

Input

Output

pre-order : 13 8 6 47 25 51

## Algorithm

We do not have to change the structure of the binary tree and convert it to Binary Search Tree. Note the property of a Binary Search Tree that the inorder traversal of a Binary Search Tree leads to the sorted data. We will use this property to achieve the desired result.

The idea is to store the inorder traversal of Binary Tree into an array, sort the array and then traverse the array and Binary Tree(in inorder form) and replace every node in the Binary Tree with the corresponding element in the array. This will convert the Binary Tree to Binary Search Tree.

1. Create an array, named inOrder.
2. Traverse the given Binary Tree in in-order form and store the value of nodes in the array ‘inOrder’.
3. Sort the array.
4. Simultaneously traverse the array and Binary Tree in in-order form and replace the corresponding node’s value in Binary Tree with the value in inOrder array.
5. The Binary Tree is converted to Binary Search Tree.

Time Complexity = O(n log(n))
Space Complexity = O(n), as we used an array to store the in-order traversal
where n is the number of node in given Binary Tree.

READ  Check if the given array can represent Level Order Traversal of Binary Search Tree

## Explanation

Consider the binary tree shown in the example above.

Step 1 & 2

Store the in-order traversal of Binary Tree in an array.
inOrder[] = {47, 51, 25, 6, 13, 8}

Step 3

Sort the array.
inOrder = {6, 8, 13, 25, 47, 51}

Step 4

Simultaneously traverse the array and Binary Tree and replace the element of a binary tree with the corresponding element of the sorted inOrder array.
The Binary Tree now looks like,

The Binary Tree is converted to Binary Search Tree.

## JAVA Code for Binary Tree to Binary Search Tree Conversion

```import java.util.ArrayList;
import java.util.Collections;

public class BinaryTreeToBinarySearchTreeConversion {
// class representing Node of a Binary Tree
static class Node {
int data;
Node left, right;

public Node(int data) {
this.data = data;
}
}

// class to provide a wrapper around index
// so that we can pass it by reference
static class Index {
int index;

public Index(int index) {
this.index = index;
}
}

// function to print pre order traversal of a binary tree
private static void preOrder(Node root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
}

// function to traverse in binary tree in in-order form and store the elements
// in a list
private static void inOrderAndFormList(Node root, ArrayList<Integer> inorder) {
if (root != null) {
inOrderAndFormList(root.left, inorder);
// store the current value in the list
inOrderAndFormList(root.right, inorder);
}
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
private static void inOrderAndChange(Node root, ArrayList<Integer> inOrder, Index index) {
if (root != null) {
inOrderAndChange(root.left, inOrder, index);
// change the current element of Tree with current element of list
root.data = inOrder.get(index.index);
// increment index by 1
index.index++;
inOrderAndChange(root.right, inOrder, index);
}
}

private static void convertToBST(Node root) {
// create a list and store the inorder of the given Binary Tree
ArrayList<Integer> inOrder = new ArrayList<>();
inOrderAndFormList(root, inOrder);

// Sort the list
Collections.sort(inOrder);

// traverse in binary tree and list simultaneously and change the required values
inOrderAndChange(root, inOrder, new Index(0));
}

public static void main(String[] args) {
// Example Tree
Node root = new Node(25);
root.left = new Node(51);
root.right = new Node(13);
root.left.left = new Node(47);
root.right.left = new Node(6);
root.right.right = new Node(8);

convertToBST(root);

preOrder(root);
System.out.println();
}
}```
`13 8 6 47 25 51`

## C++ Code for Binary Tree to Binary Search Tree Conversion

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// class representing Node of a Binary Tree
class Node {
public:
int data;
Node *left;
Node *right;

Node(int d) {
data = d;
}
};

// global variable index
int index = 0;

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

// function to traverse in binary tree in in-order form and store the elements
// in a list
void inOrderAndFormList(Node *root, vector<int> &inOrder) {
if (root != NULL) {
inOrderAndFormList(root->left, inOrder);
// store the current value in the list
inOrder.push_back(root->data);
inOrderAndFormList(root->right, inOrder);
}
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
void inOrderAndChange(Node *root, vector<int>& inOrder) {
if (root != NULL) {
inOrderAndChange(root->left, inOrder);

// change the current element of Tree with current element of list
root->data = inOrder[index];
index++;

inOrderAndChange(root->right, inOrder);
}
}

void convertToBST(Node *root) {
// create a list and store the inorder of the given Binary Tree
vector<int> inOrder;
inOrderAndFormList(root, inOrder);

// Sort the list
sort(inOrder.begin(), inOrder.end());

// traverse in binary tree and list simultaneously and change the required values
index = 0;
inOrderAndChange(root, inOrder);
}

int main() {
// Example Tree
Node *root = new Node(25);
root->left = new Node(51);
root->right = new Node(13);
root->left->left = new Node(47);
root->right->left = new Node(6);
root->right->right = new Node(8);

convertToBST(root);

preOrder(root);
cout<<endl;

return 0;
}```
`13 8 6 47 25 51`

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions