Java program to convert Binary Tree to Binary Search Tree

Converting a Binary Tree to a Binary Search Tree involves two steps :

* Traverse the Binary Tree in in-order traversal to get a sorted array of all the nodes.
* Build a Binary Search Tree from the sorted array of nodes.

Here's the Java program to convert a Binary Tree to a Binary Search Tree :

Program :

import java.util.*;

class Node {
    int data;
    Node left, right;

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

class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    // In-order traversal of Binary Tree
    void inOrder(Node node, List<Integer> list) {
        if (node == null)
            return;
        inOrder(node.left, list);
        list.add(node.data);
        inOrder(node.right, list);
    }

    // Build Binary Search Tree from sorted array
    Node sortedArrayToBST(int[] arr, int start, int end) {
        if (start > end)
            return null;

        int mid = (start + end) / 2;
        Node node = new Node(arr[mid]);

        node.left = sortedArrayToBST(arr, start, mid - 1);
        node.right = sortedArrayToBST(arr, mid + 1, end);

        return node;
    }

    // Convert Binary Tree to Binary Search Tree
    void convertBTtoBST() {
        // Get sorted list of all nodes in Binary Tree
        List<Integer> nodeList = new ArrayList<>();
        inOrder(root, nodeList);
        int[] arr = new int[nodeList.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = nodeList.get(i);
        }

        // Build Binary Search Tree from sorted array
        root = sortedArrayToBST(arr, 0, arr.length - 1);
    }

    // Print Binary Tree in in-order traversal
    void printInOrder(Node node) {
        if (node == null)
            return;
        printInOrder(node.left);
        System.out.print(node.data + " ");
        printInOrder(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(2);
        tree.root.right = new Node(7);
        tree.root.left.left = new Node(8);
        tree.root.left.right = new Node(4);

        System.out.println("Binary Tree:");
        tree.printInOrder(tree.root);

        tree.convertBTtoBST();

        System.out.println("\n\nBinary Search Tree:");
        tree.printInOrder(tree.root);
    }
}

Output :

Binary Tree:8 2 4 10 7 

Binary Search Tree:
8 2 4 10 7

In this program, we first define a Node class to represent each node in the Binary Tree, and a BinaryTree class to represent the Binary Tree itself. We define methods for in-order traversal, building a Binary Search Tree from a sorted array, and converting a Binary Tree to a Binary Search Tree.

To convert a Binary Tree to a Binary Search Tree, we first traverse the Binary Tree in in-order traversal to get a sorted list of all the nodes. We then convert the sorted list to an array and build a Binary Search Tree from the array using a recursive method that creates a new node for the middle element of the array, and recursively calls itself on the left and right halves of the array to create the left and right subtrees.

Finally, we test the program by creating a sample Binary Tree and printing it in in-order traversal before and after conversion to a Binary Search Tree.