Leetcode - 108. Convert Sorted Array to Binary Search Tree

#leetcode

When you’re given a sorted array, you might be asked to convert it into a height-balanced binary search tree (BST). A BST is called height-balanced if the depth of the two subtrees of every node never differs by more than one.

This problem comes up often in interviews because it beautifully combines recursion, binary search thinking, and tree construction.

💡 Intuition

Since the array is sorted, the middle element naturally makes the best root:

Everything to the left of the middle is smaller → belongs to the left subtree.
Everything to the right of the middle is larger → belongs to the right subtree.

By always picking the middle element as the root (and recursively repeating this for subarrays), we ensure the tree stays as balanced as possible.

For example:

nums = [-10, -3, 0, 5, 9]

Step 1: Pick middle → 0 (root)
            0
           / \
Step 2:  -10   5
             \    \
Step 3:      -3    9

This results in a height-balanced BST.

🛠️ Approach

Use recursion with two pointers (l and r) to define the current subarray.
Base case: if l > r, return null (no tree to build).
Find the middle index:

   let m = Math.floor((l + r) / 2);

Create a new TreeNode with nums[m].
Recursively build:

Left subtree → helper(l, m - 1)
Right subtree → helper(m + 1, r)
1. Return the node.

📜 Code (JavaScript)

/**
 * 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) {
    const helper = (l, r) => {
        if (l > r) return null;

        let m = Math.floor((l + r) / 2);
        let node = new TreeNode(nums[m]);

        node.left = helper(l, m - 1);
        node.right = helper(m + 1, r);

        return node;
    }

    return helper(0, nums.length - 1);
};

⏱️ Complexity Analysis

Time Complexity: O(n)
Each element in the array becomes a node in the tree exactly once.
Space Complexity: O(log n) (average case, due to recursion stack depth)
Since the tree is balanced, the maximum recursive calls go as deep as the height of the tree, which is log n.
In the worst case (if array is skewed or large recursion overhead), it can be O(n).

✨ Key Takeaways

Sorted array + middle element logic → perfectly balanced BST.
Divide-and-conquer strategy keeps the tree height minimal.
This is a classic recursion problem that also reinforces binary search thinking.

DEV Community