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

In this post, We will learn How do you convert a binary tree to a binary search tree in Java?

First of all, Let’s try to understand the difference between binary and binary search trees?

Binary Tree

A tree is called a binary tree if each note has zero children, one child, or two children, an empty tree is also a valid binary tree. we can visualize a binary tree consisting of a root and two disjoint binary trees called the left and right subtrees of the root.

Binary Search Tree (BST)

Binary Search Tree or BST is a node-based binary tree data structure which are having the following properties:

The left subtree of a node contains only nodes with values smaller value than the root node’s value.
The right subtree of a node contains only nodes with values greater than the root node’s value.
The left and right subtrees are also must be a binary search tree.
You should note that Binary Search Tree(BST) must not be duplicate nodes.

Now Let’s discuss how to convert a binary tree to BST (Binary Search Tree) by maintaining its original structure

For example, consider binary tree is shown on the left side and it should be converted to BST shown on the right

Here the idea is to traverse the binary tree and store its keys in a TreeSet. We know that an in-order traversal of a binary search tree returns the nodes in sorted order so we have to traverse the tree again in in-order fashion and put the keys present in the TreeSet (in sorted order) back to their correct position in BST.

The advantage of using TreeSet over other data structures is that the keys are always retrieved in sorted order from TreeSet. if we use other data structure then we have to sort the keys first before inserting them back.

The time complexity of this solution is O (n log n) and auxiliary space taken by the program is O(n)

Below is the Complete Source code:

Node.java

package com.kkjavatutorials.tree;
import java.util.Iterator;
/**
 * This Class is used to store a Binary
 * Search Tree node
 * @author KK JavaTutorials
 */
public class Node {

	public int data;
	public Node left;
	public Node right;

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

	/**
	 * Method to perform in-order traversal of the tree
	 * @param root Binary Tree
	 */
	public void inOrder(Node root) {
		if (root == null) {
			return;
		}

		inOrder(root.left);
		System.out.print(root.data + " ");
		inOrder(root.right);
	}

	/**
	 * Method to keep keys in set in their correct
	 * order in BST by doing in-order traversal
	 * @param root Binary Tree
	 * @param itr 
	 */
	public void convertBinaryTreeToBST(Node root, Iterator<Integer> itr) {
		if (root == null) {
			return;
		}

		convertBinaryTreeToBST(root.left, itr);
		root.data = itr.next();
		convertBinaryTreeToBST(root.right, itr);
	}
}

package com.kkjavatutorials.tree;

import java.util.Iterator;

/**

* This Class is used to store a Binary

* Search Tree node

* @author KK JavaTutorials

public class Node {

public int data;

public Node left;

public Node right;

public Node(int data) {

this.data = data;

}

/**

* Method to perform in-order traversal of the tree

* @param root Binary Tree

public void inOrder(Node root) {

if (root == null) {

return;

}

inOrder(root.left);

System.out.print(root.data + " ");

inOrder(root.right);

}

/**

* Method to keep keys in set in their correct

* order in BST by doing in-order traversal

* @param root Binary Tree

* @param itr

public void convertBinaryTreeToBST(Node root, Iterator<Integer> itr) {

if (root == null) {

return;

}

convertBinaryTreeToBST(root.left, itr);

root.data = itr.next();

convertBinaryTreeToBST(root.right, itr);

}

ClientTest.java

package com.kkjavatutorials.client;

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

import com.kkjavatutorials.tree.Node;

/**
 *Client Program to convert a binary tree to a
 *binary search tree(BST) 
 * @author KK JavaTutorials
 */
public class ClientTest {
	public static void main(String[] args) {

		//Create root node
		Node root = new Node(8);
		root.left = new Node(3);
		root.right = new Node(5);
		root.left.left = new Node(10);
		root.left.right = new Node(2);
		root.right.left = new Node(4);
		root.right.right = new Node(6);

		System.out.println("Original Binary Tree..");
		root.inOrder(root);
		
		//Traversing the binary tree and storing its keys in a set
		Set<Integer> set = new TreeSet<>();
		extractKeysFromBinaryTree(root, set);

		//Putting back keys present in set in their correct order in BST
		Iterator<Integer> itr = set.iterator();
		root.convertBinaryTreeToBST(root, itr);

		System.out.println();
		System.out.println("After converting into Binary Search Tree..");
		//Printing the BST
		root.inOrder(root);
	}

	/**
	 * Method to traverse the binary tree
	 * and store its keys in a set
	 * @param root binary tree
	 * @param set
	 */
	public static void extractKeysFromBinaryTree(Node root, Set<Integer> set) {
		// base case
		if (root == null) {
			return;
		}

		extractKeysFromBinaryTree(root.left, set);
		set.add(root.data);
		extractKeysFromBinaryTree(root.right, set);
	}
}

package com.kkjavatutorials.client;

import java.util.Iterator;

import java.util.Set;

import java.util.TreeSet;

import com.kkjavatutorials.tree.Node;

/**

*Client Program to convert a binary tree to a

*binary search tree(BST)

* @author KK JavaTutorials

public class ClientTest {

public static void main(String[] args) {

//Create root node

Node root = new Node(8);

root.left = new Node(3);

root.right = new Node(5);

root.left.left = new Node(10);

root.left.right = new Node(2);

root.right.left = new Node(4);

root.right.right = new Node(6);

System.out.println("Original Binary Tree..");

root.inOrder(root);

//Traversing the binary tree and storing its keys in a set

Set<Integer> set = new TreeSet<>();

extractKeysFromBinaryTree(root, set);

//Putting back keys present in set in their correct order in BST

Iterator<Integer> itr = set.iterator();

root.convertBinaryTreeToBST(root, itr);

System.out.println();

System.out.println("After converting into Binary Search Tree..");

//Printing the BST

root.inOrder(root);

}

/**

* Method to traverse the binary tree

* and store its keys in a set

* @param root binary tree

* @param set

public static void extractKeysFromBinaryTree(Node root, Set<Integer> set) {

// base case

if (root == null) {

return;

}

extractKeysFromBinaryTree(root.left, set);

set.add(root.data);

extractKeysFromBinaryTree(root.right, set);

}

The output of This Program:

Original Binary Tree..
10 3 2 8 4 5 6
After converting into Binary Search Tree..
2 3 4 5 6 8 10

You May Also Like:

Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Search operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
Find the node with minimum and maximum values in a Binary Search Tree
Find a mirror image of a binary tree

That’s all about How do you convert a binary tree to a binary search tree(BST) in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply Cancel reply