Convert Sorted Array to Binary Search Tree

LeetCode 108 | Difficulty: Easy

Easy

Problem Description

Given an integer array nums where the elements are sorted in ascending order, convert *it to a *height-balanced binary search tree.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

- `1 <= nums.length <= 10^4`

- `-10^4 <= nums[i] <= 10^4`

- `nums` is sorted in a **strictly increasing** order.

Topics: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

---

Approach

Direct Approach

This problem can typically be solved with straightforward iteration or simple data structure usage. Focus on correctness first, then optimize.

When to use

Basic problems that test fundamental programming skills.

---

Solutions

Solution 1: C# (Best: 112 ms)

Metric	Value
Runtime	112 ms
Memory	11.2 MB
Date	2019-02-02

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode SortedArrayToBST(int[] nums)
          {
              return SortedArrayToBST(nums, 0, nums.Length-1);
          }

          public TreeNode SortedArrayToBST(int[] nums, int low, int high)
          {
              if(low>high) return null;
              int mid = low + (high-low)/2;
              TreeNode root = new TreeNode(nums[mid]);
              root.left = SortedArrayToBST(nums, low, mid-1);
              root.right = SortedArrayToBST(nums, mid+1, high);

              return root;
          }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.