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 Tree Example

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.

Binary Search Tree

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

Binary Tree To BST

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: 

ConvertBinaryTreeIntoBinarySearchTree

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:

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

Your email address will not be published.