Java: Convert an sorted array to binary search tree

Last update on April 01 2025 10:53:20 (UTC/GMT +8 hours)

Array to Minimal Height BST

Write a Java program to convert an array of sorted items into a binary search tree. Maintain the minimal height of the tree.

Sample Solution:

Java Code:

public class Solution {
    public static void main(String[] args) {
        // Define an array of sorted integers
        int[] arr = {1, 2, 3, 4, 5, 6};
        
        // Convert the sorted array to a balanced binary search tree (BST)
        TreeNode root = sortedArrayToBST(arr);
        
        // Traverse the BST and print the values
        traverseTree(root);
    }

    public static TreeNode sortedArrayToBST(int[] arr) {
        if (arr.length == 0) return null;
        
        // Call the recursive function for creating the BST
        return creation(arr, 0, arr.length - 1);
    }

    private static TreeNode creation(int[] arr, int start, int end) {
        TreeNode node = new TreeNode(0);
        
        if (start == end - 1) {
            // If the range contains two elements, create the nodes accordingly
            node = new TreeNode(arr[start]);
            node.right = new TreeNode(arr[end]);
        } else if (start == end) {
            // If the range contains a single element, create a node
            return new TreeNode(arr[start]);
        } else {
            // Calculate the middle index of the range
            int mid = (start + end) / 2;
            
            // Set the value of the current node to the middle element
            node.val = arr[mid];
            
            // Recursively create left and right subtrees
            node.left = creation(arr, start, mid - 1);
            node.right = creation(arr, mid + 1, end);
        }
        return node;
    }

    private static void traverseTree(TreeNode root) {
        // Post-order traversal of the BST (left, right, root)
        if (root != null) {
            traverseTree(root.left);
            traverseTree(root.right);
            System.out.println(root.val);
        }
    }
}

class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

Sample Output:

2
1
4
6
5
3

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Java program to construct a balanced BST from an unsorted array.
• Write a Java program to construct a minimal height BST from an array containing duplicate elements.
• Write a Java program to create a BST from an array and print its level-order traversal.
• Write a Java program to check if a given BST formed from an array maintains minimal height.

Java Code Editor:

Previous: Write a Java program to remove the nth element from the end of a given list.
Next: Write a Java program to find the number of bits required to flip to convert two given integers.