108. Convert Sorted Array to Binary Search Tree

Array Tree Binary Search Tree Binary Tree Divide and Conquer

Time: O(n)

Space: O(log n)

Intuition

The middle element of a sorted array becomes the root of the BST (ensuring height balance). Recurse on the left half for the left subtree and on the right half for the right subtree.

Algorithm

1If left > right, return null.
2mid = left + (right - left) / 2.
3Create node with nums[mid].
4node.left = Build(left, mid-1). node.right = Build(mid+1, right).
5Return node.

Example Walkthrough

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

1.mid=2 (0) -> root=0.
2.Left: [-10,-3] -> mid=0(-10)... mid=-10, right: [-3] -> -3.
3.Right: [5,9] -> mid=5, right: [9] -> 9.

Output: BST [0,-3,9,-10,null,5]

Common Pitfalls

•For even-length arrays, either mid=(left+right)/2 or mid=(left+right+1)/2 is valid - the judge accepts both.

108.cs

// Approach: Recursively pick the middle element of the sorted subarray as
// the root to ensure height balance.
// Time: O(n) Space: O(log n)

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

public class Solution
{
    public TreeNode SortedArrayToBST(int[] nums)
    {
        return Build(nums, 0, nums.Length - 1);
    }

    private TreeNode Build(int[] nums, int l, int r)
    {
        if (l > r)
            return null;
        int m = (l + r) / 2;
        return new TreeNode(nums[m], Build(nums, l, m - 1), Build(nums, m + 1, r));
    }
}

Was this solution helpful?