# LeetCode 109: Convert Sorted List to Binary Search Tree

## Problem Restatement

We are given the head of a singly linked list whose values are sorted in ascending order.

We need to convert this sorted linked list into a height-balanced binary search tree.

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

The resulting tree must satisfy the BST property:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head`, the head of a sorted singly linked list |
| Output | The root of a height-balanced BST |
| List order | Ascending |
| Important condition | The resulting BST must be balanced |
| Linked list property | Sequential access only |

LeetCode gives these classes:

```python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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 sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        ...
```

## Examples

Consider the linked list:

```text
-10 -> -3 -> 0 -> 5 -> 9
```

The middle value is:

```python
0
```

This is a good root because it splits the values into two nearly equal halves.

Left half:

```text
-10 -> -3
```

Right half:

```text
5 -> 9
```

One valid BST is:

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

Another valid balanced BST is also acceptable.

For:

```text
1 -> 3
```

One valid answer is:

```text
    3
   /
  1
```

Another valid answer is:

```text
    1
     \
      3
```

Both are balanced BSTs.

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

For a sorted array, we can directly access the middle index.

But a linked list does not support indexing.

So we need another way to find the middle value efficiently.

The standard method uses two pointers:

```text
slow pointer
fast pointer
```

The slow pointer moves one step at a time.

The fast pointer moves two steps at a time.

When the fast pointer reaches the end, the slow pointer is at the middle node.

That middle node becomes the BST root.

## Key Insight

The middle node naturally divides the linked list into:

```text
left half
middle node
right half
```

Because the list is sorted:

```text
left values  < middle value
right values > middle value
```

So the BST property automatically holds.

Then we recursively build:

```text
left subtree  from left half
right subtree from right half
```

To isolate the left half, we disconnect the list before the middle node.

## Algorithm

Define a recursive function:

```python
build(head)
```

For each call:

1. If `head` is `None`, return `None`.
2. If the list contains only one node, return a leaf node.
3. Use slow and fast pointers to find the middle node.
4. Disconnect the left half from the middle node.
5. Create a tree node using the middle value.
6. Recursively build the left subtree from the left half.
7. Recursively build the right subtree from the nodes after the middle.
8. Return the root node.

The middle node is found using:

```python
slow = head
fast = head
```

Then:

```python
slow moves by 1
fast moves by 2
```

When the loop finishes, `slow` points to the middle node.

## Correctness

The algorithm always chooses the middle node of the current linked list as the subtree root.

Since the linked list is sorted, every value before the middle node is smaller, and every value after the middle node is larger. Therefore, the BST property holds at the current root.

The algorithm disconnects the left half and recursively builds the left and right subtrees from the two remaining sublists. The same reasoning applies recursively to every subtree.

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

When the list becomes empty, the algorithm returns `None`, correctly representing a missing child. When the list contains one node, the algorithm returns a leaf node.

Thus, the final tree is both a valid binary search tree and height-balanced.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Each recursive level scans list segments to find middle nodes |
| Space | `O(log n)` | Recursion depth follows tree height |

Here, `n` is the number of nodes in the linked list.

Finding the middle node costs linear time for each recursive segment.

## Implementation

```python
from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

# 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 sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if head is None:
            return None

        if head.next is None:
            return TreeNode(head.val)

        prev = None
        slow = head
        fast = head

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        prev.next = None

        root = TreeNode(slow.val)

        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)

        return root
```

## Code Explanation

The empty list case:

```python
if head is None:
    return None
```

A single-node list becomes a leaf node:

```python
if head.next is None:
    return TreeNode(head.val)
```

Initialize the pointers:

```python
prev = None
slow = head
fast = head
```

The loop finds the middle node:

```python
while fast and fast.next:
    prev = slow
    slow = slow.next
    fast = fast.next.next
```

`slow` moves one step.

`fast` moves two steps.

When the loop finishes:

```python
slow
```

points to the middle node.

Disconnect the left half:

```python
prev.next = None
```

Create the root node:

```python
root = TreeNode(slow.val)
```

Build the left subtree from the left half:

```python
root.left = self.sortedListToBST(head)
```

Build the right subtree from the nodes after the middle:

```python
root.right = self.sortedListToBST(slow.next)
```

Finally:

```python
return root
```

## Testing

We can test correctness by checking:

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

```python
from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if head is None:
            return None

        if head.next is None:
            return TreeNode(head.val)

        prev = None
        slow = head
        fast = head

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        prev.next = None

        root = TreeNode(slow.val)

        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)

        return root

def build_list(values):
    dummy = ListNode()
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

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()

    values1 = [-10, -3, 0, 5, 9]
    root1 = s.sortedListToBST(build_list(values1))
    assert inorder(root1) == values1
    assert is_balanced(root1)

    values2 = [1, 3]
    root2 = s.sortedListToBST(build_list(values2))
    assert inorder(root2) == values2
    assert is_balanced(root2)

    values3 = [1]
    root3 = s.sortedListToBST(build_list(values3))
    assert inorder(root3) == values3
    assert is_balanced(root3)

    values4 = [-5, -2, 0, 1, 8, 10]
    root4 = s.sortedListToBST(build_list(values4))
    assert inorder(root4) == values4
    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 list |
| `[1]` | Single-node tree |
| Larger sorted list | Confirms recursive splitting and balance |