Java program to convert Binary Tree to Binary Search Tree

In this program, we need to convert given binary tree to a corresponding binary search tree. A tree is said to be the binary tree if each of the nodes has at most two children. Whereas, the binary search tree is the special case of the binary tree in which all the nodes to the left of root node should be less than root node and nodes to the right should be greater than root node.

This problem can be resolved by converting given binary tree to its corresponding array representation. Sort the array. Calculate the middle node from array elements as it will become the root node of the corresponding binary search tree.

Algorithm

Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
Define another class which has two attribute root and treeArray.
- Root represents the root node of the tree and initializes it to null.
- treeArray will store the array representation of the binary tree.

a. convertBTBST() will convert binary tree to the corresponding binary search tree:

It will convert the binary tree to corresponding array by calling convertBTtoArray().
Sort the resultant array from step 1 in ascending order.
Convert the array to the binary search tree by calling createBST().

calculateSize() will count the number of nodes present in the tree.
convertBTtoArray() will convert binary tree to its array representation by traversing the tree and adding elements to treeArray.
createBST() will create a corresponding binary search tree by selecting a middle node of sorted treeArray as it the root node. treeArray will be divided into two parts i.e [0, mid-1] and [mid+1, end]. Recursively find middle node from each array to create left subtree and right subtree respectively.
Inorder() will display the nodes of the tree in inorder fashion, i.e., left child followed by root node followed by the right child.

import java.util.Arrays; public class ConvertBTtoBST { //Represent a node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; int[] treeArray; int index = 0; public ConvertBTtoBST(){ root = null; } //convertBTBST() will convert a binary tree to binary search tree public Node convertBTBST(Node node) { //Variable treeSize will hold size of tree int treeSize = calculateSize(node); treeArray = new int[treeSize]; //Converts binary tree to array convertBTtoArray(node); //Sort treeArray Arrays.sort(treeArray); //Converts array to binary search tree Node d = createBST(0, treeArray.length -1); return d; } //calculateSize() will calculate size of tree public int calculateSize(Node node) { int size = 0; if (node == null) return 0; else { size = calculateSize (node.left) + calculateSize (node.right) + 1; return size; } } //convertBTtoArray() will convert the given binary tree to its corresponding array representation public void convertBTtoArray(Node node) { //Check whether tree is empty if(root == null){ System.out.println("Tree is empty"); return; } else { if(node.left != null) convertBTtoArray(node.left); //Adds nodes of binary tree to treeArray treeArray[index] = node.data; index++; if(node.right != null) convertBTtoArray(node.right); } } //createBST() will convert array to binary search tree public Node createBST(int start, int end) { //It will avoid overflow if (start > end) { return null; } //Variable will store middle element of array and make it root of binary search tree int mid = (start + end) / 2; Node node = new Node(treeArray[mid]); //Construct left subtree node.left = createBST(start, mid - 1); //Construct right subtree node.right = createBST(mid + 1, end); return node; } //inorder() will perform inorder traversal on binary search tree public void inorderTraversal(Node node) { //Check whether tree is empty if(root == null){ System.out.println("Tree is empty"); return; } else { if(node.left!= null) inorderTraversal(node.left); System.out.print(node.data + " "); if(node.right!= null) inorderTraversal(node.right); } } public static void main(String[] args) { ConvertBTtoBST bt = new ConvertBTtoBST(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.left.right = new Node(5); bt.root.right.left = new Node(6); bt.root.right.right = new Node(7); //Display given binary tree System.out.println("Inorder representation of binary tree: "); bt.inorderTraversal(bt.root); //Converts binary tree to corresponding binary search tree Node bst = bt.convertBTBST(bt.root); //Display corresponding binary search tree System.out.println("\nInorder representation of resulting binary search tree: "); bt.inorderTraversal(bst); } }

Java program to convert Binary Tree to Binary Search Tree

Algorithm

All Answers

Program:

Java Tree Programs

This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now