# LeetCode 108: Convert Sorted Array to Binary Search Tree

## Problem Restatement

We are given a sorted integer array `nums` in ascending order.

We need to convert it into a height-balanced binary search tree.

The official problem defines a height-balanced binary tree as a binary tree in which the depth difference between the two subtrees of every node is never more than `1`. ([leetcode.com](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/?utm_source=chatgpt.com))

The tree must also satisfy the binary search tree property:

```text
left subtree values  < root value
right subtree values > root value
```

Because the array is already sorted, we need to arrange the numbers into a balanced BST structure.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` |
| Output | The root of a height-balanced BST |
| Array order | Ascending |
| Important condition | The resulting tree must be balanced |
| BST rule | Left values smaller, right values larger |

LeetCode gives the `TreeNode` class:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```

The function shape is:

```python
class Solution:
    def sortedArrayToBST(self, nums: list[int]) -> Optional[TreeNode]:
        ...
```

## Examples

Consider:

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

The middle value is:

```python
0
```

This is a good root because it splits the array into two nearly equal halves:

```text
[-10, -3]   0   [5, 9]
```

Now recursively build the left subtree from:

```python
[-10, -3]
```

and the right subtree from:

```python
[5, 9]
```

One valid balanced BST is:

```text
         0
       /   \
     -10     5
        \     \
        -3     9
```

Another valid answer is also acceptable because the problem allows multiple balanced trees.

For:

```python
nums = [1, 3]
```

One valid tree is:

```text
    3
   /
  1
```

Another valid tree is:

```text
    1
     \
      3
```

Both are balanced BSTs.

## First Thought: Use the Middle Element as the Root

The array is already sorted.

If we always choose the smallest value as the root:

```text
1
 \
  2
   \
    3
```

the tree becomes skewed.

Similarly, always choosing the largest value also creates a skewed tree.

To keep the tree balanced, we should choose the middle element as the root.

Then:

```text
left half  -> left subtree
right half -> right subtree
```

This naturally creates balanced subtree sizes.

## Key Insight

A sorted array already contains the correct inorder traversal of a BST.

For example:

```python
[-10, -3, 0, 5, 9]
```

If we place the middle value at the root:

```python
0
```

then all smaller values stay on the left and all larger values stay on the right.

This automatically satisfies the BST property.

Then we recursively repeat the same idea for the left and right halves.

This is a divide-and-conquer problem.

## Algorithm

Define a recursive function:

```python
build(left, right)
```

This function builds a BST from:

```python
nums[left : right + 1]
```

For each recursive call:

1. If `left > right`, return `None`.
2. Compute the middle index.
3. Create a node using the middle value.
4. Recursively build the left subtree from the left half.
5. Recursively build the right subtree from the right half.
6. Return the node.

The middle index is:

```python
mid = (left + right) // 2
```

The left subtree uses:

```text
left to mid - 1
```

The right subtree uses:

```text
mid + 1 to right
```

## Correctness

The algorithm always chooses the middle value of the current subarray as the root node.

All values left of the middle index are smaller than the root because the array is sorted. All values right of the middle index are larger than the root. Therefore, the BST property holds at every node.

The recursive calls apply the same rule to the left and right halves. Thus, every subtree also satisfies the BST property.

Because the middle element splits the array into two nearly equal halves, the sizes of the left and right subtrees differ by at most one element at each step. Therefore, the resulting tree is height-balanced.

When the subarray becomes empty, the algorithm returns `None`, which correctly represents a missing child.

So the returned tree is both a valid binary search tree and height-balanced.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Every array element becomes exactly one tree node |
| Space | `O(log n)` | Recursive calls follow the tree height in a balanced tree |

Here, `n` is the number of elements in the array.

The recursion depth is logarithmic because the array is split approximately in half at every step.

## Implementation

```python
from typing import Optional

# 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: list[int]) -> Optional[TreeNode]:
        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None

            mid = (left + right) // 2

            root = TreeNode(nums[mid])

            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)

            return root

        return build(0, len(nums) - 1)
```

## Code Explanation

The helper function builds a subtree from one array range:

```python
def build(left: int, right: int):
```

If the range is empty, there is no node:

```python
if left > right:
    return None
```

Choose the middle index:

```python
mid = (left + right) // 2
```

Create the root node using the middle value:

```python
root = TreeNode(nums[mid])
```

Build the left subtree from the left half:

```python
root.left = build(left, mid - 1)
```

Build the right subtree from the right half:

```python
root.right = build(mid + 1, right)
```

Finally, return the constructed subtree root:

```python
return root
```

The first call uses the full array:

```python
return build(0, len(nums) - 1)
```

## Testing

To verify correctness, we can check:

1. The inorder traversal matches the original sorted array.
2. The tree is balanced.

```python
from typing import Optional

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: list[int]) -> Optional[TreeNode]:
        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None

            mid = (left + right) // 2

            root = TreeNode(nums[mid])

            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)

            return root

        return build(0, len(nums) - 1)

def inorder(root):
    if root is None:
        return []

    return inorder(root.left) + [root.val] + inorder(root.right)

def is_balanced(root):
    def height(node):
        if node is None:
            return 0

        left = height(node.left)
        right = height(node.right)

        if left == -1 or right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

def run_tests():
    s = Solution()

    nums1 = [-10, -3, 0, 5, 9]
    root1 = s.sortedArrayToBST(nums1)
    assert inorder(root1) == nums1
    assert is_balanced(root1)

    nums2 = [1, 3]
    root2 = s.sortedArrayToBST(nums2)
    assert inorder(root2) == nums2
    assert is_balanced(root2)

    nums3 = [1]
    root3 = s.sortedArrayToBST(nums3)
    assert inorder(root3) == nums3
    assert is_balanced(root3)

    nums4 = [-5, -2, 0, 1, 8, 10]
    root4 = s.sortedArrayToBST(nums4)
    assert inorder(root4) == nums4
    assert is_balanced(root4)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[-10,-3,0,5,9]` | Standard mixed values |
| `[1,3]` | Even-length array |
| `[1]` | Single-node tree |
| Larger sorted array | Confirms recursive splitting and balance |