108. Convert Sorted Array to Binary Search Tree - Leetcode Solution

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedArrayToBST(self, nums):
        def helper(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            node = TreeNode(nums[mid])
            node.left = helper(left, mid - 1)
            node.right = helper(mid + 1, right)
            return node
        return helper(0, len(nums) - 1)

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

class Solution {
public:
    TreeNode* sortedArrayToBST(vector& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
private:
    TreeNode* helper(vector& 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;
    }
};

// Definition for a binary tree node.
public 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;
    }
}

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;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    function helper(left, right) {
        if (left > right) return null;
        const mid = Math.floor((left + right) / 2);
        const node = new TreeNode(nums[mid]);
        node.left = helper(left, mid - 1);
        node.right = helper(mid + 1, right);
        return node;
    }
    return helper(0, nums.length - 1);
};

Problem Description

Given an integer array nums where the elements are sorted in ascending order, your task is to convert it into a height-balanced binary search tree (BST). A height-balanced BST is a binary tree where the depth of the two subtrees of every node never differs by more than one.

Key constraints:

Each element in nums must be used exactly once in the tree.
There is only one valid solution for each input.
Do not reuse or skip elements.
The input array nums is sorted in strictly increasing order.

The output should be the root node of the resulting balanced BST.

Thought Process

To solve this problem, we need to transform a sorted array into a balanced BST. The most natural brute-force approach might be to insert each value into a BST one by one, but this could easily lead to an unbalanced tree, especially if we always insert from left to right.

Instead, we notice that the middle element of the sorted array is the best candidate for the root of the BST, because it evenly splits the array into two halves. By recursively applying this logic to each half, we can ensure that the tree remains balanced.

Thus, the shift from brute-force to an optimized solution comes from realizing that the sorted nature of the array allows us to always pick the middle value as the root, guaranteeing balance at each level.

Solution Approach

The algorithm uses a recursive, divide-and-conquer strategy. Here is how it works step-by-step:

Identify the Middle Element: For any subarray, select the middle element as the root. This ensures that the left and right subtrees are as balanced as possible.
Recursively Build Subtrees:
- The left subtree is built from the subarray to the left of the middle element.
- The right subtree is built from the subarray to the right of the middle element.
Base Case: If the subarray is empty (left index > right index), return null (or None), as there are no nodes to add.
Recurse: Continue this process for each subtree until the entire array has been used.

Why this works: Choosing the middle element as the root at every step ensures that the tree's height is minimized, and the difference in depth between left and right subtrees never exceeds one.

Example Walkthrough

Let's take nums = [-10, -3, 0, 5, 9] as an example.

Step-by-step process:

The entire array is [-10, -3, 0, 5, 9]. The middle element is 0 (index 2). This becomes the root.
Left subarray: [-10, -3] (indices 0 to 1)
- Middle is -10 + -3 = -13 / 2 = -6.5, but since we use integer division, index 0 is the middle. So, -10 becomes the left child.
- Right subarray of [-10, -3] is just [-3] (index 1). -3 becomes the right child of -10.
Right subarray: [5, 9] (indices 3 to 4)
- Middle is index 3 (5), so 5 becomes the right child of 0.
- Right subarray of [5, 9] is just [9] (index 4). 9 becomes the right child of 5.

Final BST structure:

Root: 0
- Left: -10
  - Right: -3
- Right: 5
  - Right: 9

Each step splits the array, picks the middle, and assigns left/right children recursively.

Time and Space Complexity

Brute-force approach: If we inserted elements one by one into a BST, the worst-case time complexity would be O(n^2) (for a skewed tree).

Optimized recursive approach:

Time Complexity: O(n), where n is the number of elements in nums. Each element is visited and used exactly once to create a node.
Space Complexity: O(log n) for the recursion stack in a balanced tree (since the height is log n), plus O(n) for the nodes themselves (but that's required for the output).

The efficient divide-and-conquer ensures both time and space are optimal for the problem.

Summary

The key insight for this problem is using the sorted property of the array to always pick the middle element as the root, ensuring a balanced BST. By recursively constructing left and right subtrees from the halves of the array, we guarantee that the tree is as balanced as possible. This approach is both simple and elegant, leveraging recursion and the properties of binary search trees for optimal efficiency.

AlgoMap.io

Want Help Cracking FAANG?