Question 74 : Convert sorted array to balanced BST

Algorithm:

You might know that inorder traversal of binary search tree results in sorted array. We will use this property to convert sorted array to balanced binary search tree, so middle element of array ora sub array will always be root for that array or subarray.

• Initialise two variables start and end with 0 and arr.length -1.
• Find middle element of array using start and end.
• Make middle element root element of tree.
• Recursively traverse left subtree, find middle and make it root node of left subtree
• Recursively traverse right subtree, find middle and make it root node of right subtree.

Java code to convert sorted array to balanced binary search tree:

public class BinarySearchTreeSortedArrayMain {
    public static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;
 
        TreeNode(int data) {
            this.data = data;
        }
    }
 
    public static void preOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
 
    public static void main(String[] args) {
 
        // Creating a binary search tree
        int arr[]={10,20,30,40,50,60,70,80,90};
        TreeNode rootNode = createBinarySearchTreeFromSortedArray(arr,0,arr.length-1); 
 
        System.out.println("Preorder traversal of created binary search tree :");
        preOrder(rootNode);
 
    }
 
    public static TreeNode createBinarySearchTreeFromSortedArray(int[] arr,int start,int end) {
        if (start > end) {
            return null;
        }
 
        /* Get the middle element and make it root */
        int mid = (start + end) / 2;
        TreeNode node = new TreeNode(arr[mid]);
 
        /* Recursively construct the left subtree and make it
 left child of root */
        node.left = createBinarySearchTreeFromSortedArray(arr, start, mid - 1);
 
        /* Recursively construct right subtree and make right child of the root */
        node.right = createBinarySearchTreeFromSortedArray(arr, mid + 1, end);
 
        return node;
    }
}

When you run the above program, you will get the below output:

Preorder traversal of created binary search tree :
50 20 10 30 40 70 60 80 90

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest