Construct BST from given keys

Problem Overview

The problem "Convert Sorted Array to Binary Search Tree" is an intriguing task that involves creating a height-balanced binary search tree (BST) from a sorted array of integers. The challenge is to maintain the balance of the tree, so the chosen structure ensures minimal height.

LeetCode URL: Convert Sorted Array to Binary Search Tree

Understanding the Problem

Given a sorted integer array (in ascending order), the task is to convert it into a height-balanced binary search tree (BST). In this context, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Input

• A sorted array of integers.

Output

• A height-balanced binary search tree.

Key DSA Concepts and Theory

Binary Search Tree (BST)

A binary search tree is a binary tree where each node has a key greater than or equal to the keys of the nodes in its left subtree and less than or equal to the keys of the nodes in its right subtree. Properties of a BST include:

• Searching: Efficiently search for an item in O(log n) time.
• Insertion: Add elements maintaining the BST property, requiring O(log n) time on average.
• Traversal: In-order traversal can yield elements in sorted order.

Balanced BST

A balanced BST ensures that the search operation remains efficient. Common self-balancing BSTs include AVL Trees and Red-Black Trees. However, in this problem, you don't need to use these structures but understand balanced trees' properties for creating them manually.

Divide and Conquer

The problem leverages a divide and conquer strategy. Since the input array is sorted, the middle element can be chosen as the root of the tree. Recursively repeating this process for left and right sub-arrays helps maintain balance.

Solution Approach

To solve the problem, we implement a recursive function that:

1. Identifies the middle of the array or subarray to become the root value.
2. Recursively constructs the left subtree using the left half and the right subtree using the right half of the array.
3. Returns the constructed tree node.

This process naturally balances the tree because each recursive call works on a subtree of approximately half the size of the previous one.

C++ Code Example

#include <vector>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* sortedArrayToBST(std::vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

private:
    TreeNode* helper(std::vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = helper(nums, left, mid - 1);
        node->right = helper(nums, mid + 1, right);
        
        return node;
    }
};

Java Code Example

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

    private TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, left, mid - 1);
        node.right = helper(nums, mid + 1, right);
        
        return node;
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of elements in the input array. Each element is visited once in the recursion.

• Space Complexity: O(log n) for the recursive stack space in a balanced tree, reflective of the depth of the recursion.

Common Mistakes to Avoid

1. Incorrect Base Cases: Ensure the base case in recursion is correctly implemented so that recursion halts as expected.
2. Index Calculation Errors: Incorrect handling of mid calculations can lead to off-by-one errors or infinite recursion.

Similar Problems on LeetCode

1. LeetCode 109: Convert Sorted List to Binary Search Tree
2. LeetCode 98: Validate Binary Search Tree
3. LeetCode 108: Convert Sorted Array to Binary Search Tree

Additional Resources and References

• CLRS Book: "Introduction to Algorithms" references BST structure and operations.
• GeeksforGeeks article: "Binary Search Tree - Introduction"

Understanding the recursive method, calculation of mid indices, and implementation of binary trees are crucial to mastering this problem effectively.