Convert Sorted Array to Binary Search Tree

• Difficulty: Easy
• Topics: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree
• Link: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

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:
![](https://assets.leetcode.com/uploads/2021/02/18/btree2.jpg)

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 <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement

Given a strictly increasing integer sequence nums[0...n-1] where nums[i] ∈ [-10⁴, 10⁴] and 1 ≤ n ≤ 10⁴, construct a height-balanced binary search tree (BST) containing exactly these elements. A height-balanced BST satisfies |height(left subtree) - height(right subtree)| ≤ 1 for every node. The output format is the root node of the constructed BST, with tree serialization following LeetCode’s level-order representation.

Beginner Restatement

You have a list of numbers sorted from smallest to largest. Your task is to build a “balanced” binary search tree from these numbers. A binary search tree has the property that for any node, all numbers in its left branch are smaller, and all in its right branch are larger. “Balanced” means the tree isn’t lopsided—the heights of left and right branches at every node differ by at most 1. You need to return the root of this tree.

Mathematical Restatement

Let A = [a₀, a₁, ..., aₙ₋₁] be a strictly increasing sequence. Construct a binary tree T such that:

1. inorder(T) = A (BST property)
2. For every node v ∈ T, let h(L) and h(R) be heights of left/right subtrees. Then |h(L) - h(R)| ≤ 1.
3. The construction function f(A) returns the root node r of T.

Symbolically:
Given A with aᵢ < aᵢ₊₁, find T where:

• ∀ node x, ∀y ∈ left(x).key < x.key < ∀z ∈ right(x).key
• ∀ node x, |depth(left(x)) - depth(right(x))| ≤ 1
• {x.key | x ∈ T} = {aᵢ | 0 ≤ i < n}

Constraint Analysis

1. 1 <= nums.length <= 10⁴

   • Lower bound n=1: Tree is a single node. Must handle trivial case.
   • Upper bound n=10⁴: Requires worst-case O(n) or O(n log n) time. O(n²) unacceptable.
   • Memory: Each node stores value + two pointers → ~120KB for 10⁴ nodes (fits in RAM).

2. -10⁴ <= nums[i] <= 10⁴

   • Values fit in 16-bit signed integers. No overflow concerns in comparisons.
   • Negative and zero values allowed; BST ordering respects signed comparison.

3. nums is sorted in a strictly increasing order

   • No duplicate values → simplified BST construction (no equality handling).
   • Strict monotonicity guarantees unique median selection.
   • Critical implication: The inorder traversal is exactly the input array. This enables divide-and-conquer by selecting the middle element as root.

4. Hidden Edge Cases

   • Even-length arrays: Two possible middle indices; either yields valid height-balanced BST.
   • Empty array?: Constraint says n ≥ 1, but some implementations handle n=0 for robustness.
   • Maximum depth: Balanced tree height = ⌈log₂(n)⌉ ≤ 14 for n=10⁴, preventing recursion stack overflow with proper implementation.

2. Intuition Scaffolding

Analogies

1. Real-World Metaphor (Construction)

   Building a balanced library catalog: You have sorted book IDs. Instead of adding them sequentially (creating a long chain), you pick the middle book as the main category, then recursively apply this to left/right halves. This ensures quick access time.

2. Gaming Analogy (Skill Tree)

   In an RPG skill tree, you want abilities reachable with minimal clicks. Given a sorted list of skill levels, you place the median-level skill as the “gateway” skill, then recursively build left/right branches. This minimizes maximum clicks to reach any skill.

3. Mathematical Analogy (Binary Search)

   The problem mirrors constructing the decision path of binary search. The sorted array’s midpoint is the first comparison point in optimal binary search. Left/right subarrays become subsequent comparison points, naturally creating a balanced decision tree.

Common Pitfalls (5+ Examples)

1. Sequential Insertion Trap: Inserting elements in given order produces a degenerate linked-list (height = n), violating balance.
2. Always-Left Bias: Choosing first element as root repeatedly creates left-skewed tree.
3. Over-Engineering Balance: Trying to enforce perfect balance (left/right counts equal) for even n—both ⌊n/2⌋ and ⌈n/2⌉ as root work.
4. Copying Subarrays: Slicing array copies O(n) memory per recursion level → O(n log n) space. Should use indices.
5. Ignoring Recursion Depth: With n=10⁴, worst-case recursion depth could be n if unbalanced, but balanced recursion depth is O(log n) safe.
6. Misinterpreting “Height-Balanced”: Thinking “complete binary tree” required (all levels full except last). Actually, only height balance needed.

3. Approach Encyclopedia

Approach 1: Brute Force (Sequential Insertion)

function buildBST(nums):
    root = null
    for each num in nums:
        root = insert(root, num)  // standard BST insertion
    return root

• Time Complexity: O(n²) worst-case (degenerate tree). For sorted input, each insertion traverses full height → ∑k=1…n k = O(n²)
• Space Complexity: O(n) for tree, O(n) recursion stack for insert.
• Why it fails: Violates height-balance constraint for sorted input.

Approach 2: Divide-and-Conquer (Optimal)

Core Insight: The middle element of any sorted subarray can serve as root of a BST for that subarray, with left/right subtrees built recursively from left/right halves.

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

Step 1: Find middle of [ -10, -3, 0, 5, 9 ] → 0
        0
       / \
Step 2: Left: [-10, -3], Right: [5,9]
       0
      / \
    -3   9
    /   /
 -10   5

Pseudocode:

function sortedArrayToBST(nums):
    return build(0, nums.length - 1)

function build(left, right):
    if left > right:
        return null
    mid = left + (right - left) // 2
    node = new TreeNode(nums[mid])
    node.left = build(left, mid - 1)
    node.right = build(mid + 1, right)
    return node

Complexity Derivation:

• Time: T(n) = 2T(n/2) + O(1) → by Master Theorem, O(n).
• Space: O(log n) recursion stack for balanced tree height; O(n) for output tree.

Mathematical Proof of Balance: Let H(n) be height of tree for n nodes.
H(n) = 1 + max(H(⌊(n-1)/2⌋), H(⌈(n-1)/2⌉))
Since subtrees differ by at most 1 node, H(n) = ⌈log₂(n+1)⌉ satisfies recurrence.
Thus |H(left) - H(right)| ≤ 1 for all nodes.

4. Code Deep Dive

# 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):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        def build(left, right):
            # Base case: empty subarray
            if left > right:
                return None
            
            # Choose middle element (floor division for left bias)
            mid = left + (right - left) // 2
            
            # Recursively build subtrees
            left_subtree = build(left, mid - 1)
            right_subtree = build(mid + 1, right)
            
            # Construct node with subtrees
            return TreeNode(nums[mid], left_subtree, right_subtree)
        
        # Start recursion with full array bounds
        return build(0, len(nums) - 1)

Line-by-Line Analysis:

1. Lines 1-5: TreeNode class definition. Each node stores value and left/right children.
2. Line 9: Outer function entry point. Receives sorted list nums.
3. Line 10: Inner helper build defined to avoid passing nums repeatedly.
4. Line 13: Base case left > right indicates empty subarray → return None (no node).
5. Line 16: Midpoint calculation using (left+right)//2 avoids overflow (not needed in Python but good practice). Floor division ensures left subtree gets equal or one more node when even length.
6. Lines 19-20: Recursive calls build left/right subtrees from appropriate subranges.
7. Line 23: Node constructed with value at nums[mid] and the two subtrees.
8. Line 26: Initiate recursion over entire array.

Edge Case Handling:

• n=1: left=0, right=0 → mid=0, both recursive calls hit base case (left>right) → returns single node.
• n=2: Example [1,3]:
  First call: left=0, right=1, mid=0 → root=1, left subtree empty, right subtree built from [3] → yields 1.right=3.
  Alternative interpretation: Using mid = (left+right+1)//2 would produce 3 as root.
• Large n=10⁴: Recursion depth ≈ log₂(10000) ≈ 14, safe within default recursion limits.

5. Complexity War Room

Hardware-Aware Analysis

• Time: O(n) operations. At 10⁴ elements, ~10⁴ node creations + 10⁴ recursive calls → trivial (<1ms on modern CPU).
• Space:
  • Output Tree: 10⁴ nodes × (8 bytes pointer × 2 + 4 bytes int) ≈ 200KB.
  • Recursion Stack: Depth ≤ 14 frames × ~48 bytes/frame ≈ 672 bytes.
  • Total: Fits entirely in L2/L3 cache (2-8MB), enabling fast execution.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force Insertion	O(n²)	O(n)	8/10	❌ Fails large n
Convert to Linked List then Balance	O(n)	O(n)	6/10	⚠️ Overcomplicated
Divide & Conquer (Optimal)	O(n)	O(log n) stack	9/10	✅ Recommended
Iterative with Stack	O(n)	O(log n)	7/10	✅ Acceptable

Trade-off Analysis: The recursive D&C approach maximizes readability and directly mirrors the mathematical intuition. Iterative versions (using explicit stack) reduce recursion overhead but increase code complexity for minimal gain given n ≤ 10⁴.

6. Pro Mode Extras

Variants Section

1. Sorted Linked List to BST (LeetCode 109)

   • Challenge: Cannot random access middle in O(1). Solutions:
     • Convert to array → O(n) space.
     • Two-pointer slow/fast to find middle → O(n log n) time.
     • In-order simulation → O(n) time, O(log n) space.

2. Balanced BST from Postorder/Preorder

   • Given postorder sorted? Actually sorted postorder is reverse sorted → similar problem.
   • Preorder sorted is just sorted array → same as current problem.

3. Minimal-Height BST with Duplicates

   • With duplicates, definition of BST must specify left ≤ node < right or left < node ≤ right.
   • Balance condition remains; median selection must handle equal elements.

4. Convert BST to Sorted Array (Reverse Problem)

   • Simple in-order traversal O(n) time.

Interview Cheat Sheet

Must-Mention Points:

1. “The inorder traversal of a BST is sorted → given sorted array is inorder traversal.”
2. “Choosing middle element ensures equal distribution of nodes for balance.”
3. “Time complexity O(n), space O(log n) for recursion stack.”
4. “For even n, either middle element works—both produce valid balanced trees.”

Common Follow-ups:

• “How would you handle streaming sorted data?” → Use self-balancing BST (AVL/Red-Black).
• “What if you needed to support insertions after construction?” → Augment with balance factors.

Implementation Nuances:

• Python recursion limit ~1000, but depth ≤ 14 safe.
• In C++, use int mid = left + (right-left)/2 to avoid overflow.
• In Java, consider TreeNode class as static nested class.

Testing Checklist:

• Single element array
• Two elements (both valid outputs)
• Odd/even length arrays
• Large array (10⁴ elements)
• Negative/zero/positive mix