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

By | July 16, 2020

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

ClientTest.java

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:

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.