Convert Sorted Array to Binary Search Tree - Java Solution

1. Introduction

In this post, we'll explore a common problem in binary trees: converting a sorted array into a height-balanced binary search tree (BST). A height-balanced BST is one where the depth of the two subtrees of every node never differs by more than one. This problem is key in understanding how to construct efficient and balanced search trees from sorted data.

Problem

Given an integer array nums sorted in ascending order, the task is to convert it into a height-balanced binary search tree. The goal is to ensure that the depth of the subtrees of any node in the resulting tree does not differ by more than one.

2. Solution Steps

1. Identify the middle element of the array to serve as the root of the BST.

2. Recursively apply this process to the left half of the array to build the left subtree.

3. Recursively apply this process to the right half of the array to build the right subtree.

4. Continue this process until the entire array is converted into a BST.

5. Return the root of the constructed BST.

3. Code Program

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

    TreeNode(int x) {
        val = x;
    }
}

public class SortedArrayToBST {
    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sortedArrayToBST(nums);
        // Output can be verified by performing an inorder traversal or other tree traversal methods
    }

    // Function to convert a sorted array into a height-balanced BST
    public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return constructBSTRecursive(nums, 0, nums.length - 1);
    }

    // Helper function to construct BST recursively
    private static TreeNode constructBSTRecursive(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // Middle element to balance the tree
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);

        // Construct left and right subtrees
        node.left = constructBSTRecursive(nums, left, mid - 1);
        node.right = constructBSTRecursive(nums, mid + 1, right);

        return node;
    }
}

Output:

The output will be the root of the height-balanced binary search tree. The tree structure can be verified through tree traversal methods.

Explanation:

1. sortedArrayToBST: This function initiates the conversion of a sorted array into a height-balanced BST. It handles the case where the array is empty and calls the recursive helper function constructBSTRecursive.

2. constructBSTRecursive: A recursive function that constructs the BST. It finds the middle element of the current subarray and makes it the root of the BST. This ensures that the tree remains height-balanced.

3. The function then recursively constructs the left and right subtrees using the left and right halves of the array, respectively.

4. The base case for the recursion is when the left index exceeds the right, indicating that the subarray is empty.

5. This approach ensures that the resulting BST is height-balanced, as each subtree is built from a subarray of approximately equal length.