Technical Interview Question

Problem Statement

Given a sorted array of integers, write a function to convert the array into a Binary Search Tree (BST). Return the root of the BST.

Example

Input: [-10, -3, 0, 5, 9]

Output:

      0
     / \
   -3   9
   /    /
-10    5

Function Signature

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public TreeNode sortedArrayToBST(int[] nums)

Answer:

To solve this problem, we can follow a recursive approach. The idea is to find the middle element of the array and set it as the root of the BST. Then, we recursively construct the left and right subtrees.

Below is the step-by-step explanation of the solution:

1. Define the sortedArrayToBST function to take in the sorted array of integers.
2. Start by creating a helper function buildBST which will take in the array, start index, end index and construct a BST from the given array.
3. In the sortedArrayToBST function, call the buildBST function with the given array, start index 0, and end index nums.length - 1, and return the root of the BST.

public TreeNode sortedArrayToBST(int[] nums) {
    return buildBST(nums, 0, nums.length - 1);
}

private TreeNode buildBST(int[] nums, int start, int end) {
    if (start > end) {
        return null;
    }

    int mid = (start + end) / 2; // Find the middle index
    TreeNode root = new TreeNode(nums[mid]); // Set the middle element as the root

    root.left = buildBST(nums, start, mid - 1); // Recursively build left subtree
    root.right = buildBST(nums, mid + 1, end); // Recursively build right subtree

    return root; // Return the root of the BST
}

The buildBST helper function recursively constructs the Binary Search Tree. At each step, it finds the middle index of the subarray and sets it as the root of the subtree. Then, it separately constructs the left and right subtrees by recursively calling buildBST on the left and right halves of the array.

This algorithm has a time complexity of O(n), where n is the number of elements in the input array. The reason is that for each subtree, we only traverse each element once to construct the BST. Hence, we have a linear time complexity.

Now, the sortedArrayToBST function calls the buildBST helper function and returns the root of the constructed Binary Search Tree.