# LeetCode 426: Convert Binary Search Tree to Sorted Doubly Linked List

## Problem Restatement

We are given the root of a binary search tree.

We need to convert the tree into a sorted circular doubly linked list in-place.

“In-place” means we should reuse the existing tree nodes. We should not create new list nodes.

After conversion:

| Tree Pointer | List Meaning |
|---|---|
| `left` | previous node |
| `right` | next node |

The returned node should be the smallest node in the list.

The list must also be circular:

| Node | Required Link |
|---|---|
| smallest node | `left` points to the largest node |
| largest node | `right` points to the smallest node |

For example, if the BST contains values:

```python
[1, 2, 3, 4, 5]
```

then the final doubly linked list should be:

```text
1 <-> 2 <-> 3 <-> 4 <-> 5
```

and also circular:

```text
5 -> 1
1 -> 5
```

The official problem asks for a sorted circular doubly linked list and requires the conversion to be done in-place. The left pointer becomes the predecessor pointer, and the right pointer becomes the successor pointer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root node of a BST |
| Output | The smallest node in the converted circular doubly linked list |
| In-place | Reuse the original nodes |
| Empty tree | Return `None` |
| Ordering | Nodes must appear in ascending order |

The node definition is usually given as:

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

## Examples

Consider this BST:

```text
        4
       / \
      2   5
     / \
    1   3
```

The inorder order is:

```text
1, 2, 3, 4, 5
```

So the converted list should be:

```text
1 <-> 2 <-> 3 <-> 4 <-> 5
```

Because the list is circular:

```text
1.left  = 5
5.right = 1
```

The returned node should be `1`, because it is the smallest node.

For a single-node tree:

```text
1
```

The result is a circular list with one node:

```text
1.right = 1
1.left  = 1
```

For an empty tree:

```python
root = None
```

we return:

```python
None
```

## First Thought: Collect Values or Nodes

A simple approach is:

1. Traverse the BST in sorted order.
2. Store all nodes in an array.
3. Link adjacent nodes in the array.
4. Connect the last node back to the first node.

For example, after inorder traversal:

```python
nodes = [1, 2, 3, 4, 5]
```

we link:

```text
1.right = 2
2.left  = 1

2.right = 3
3.left  = 2

...
```

Then make the list circular:

```text
5.right = 1
1.left  = 5
```

This works, but it uses an extra array of size `n`.

We can do better.

## Key Insight

A binary search tree gives sorted values through inorder traversal.

For a BST, inorder traversal visits nodes in this order:

```text
left subtree -> current node -> right subtree
```

Because of the BST property, this order is ascending.

So while doing inorder traversal, we can directly connect each visited node to the node visited immediately before it.

We only need two pointers:

| Pointer | Meaning |
|---|---|
| `head` | The smallest node, first node in the list |
| `prev` | The previously visited node during inorder traversal |

When we visit a node:

1. If `prev` exists, connect `prev` and the current node.
2. If `prev` does not exist, the current node is the first node, so it becomes `head`.
3. Move `prev` to the current node.

After traversal finishes, `prev` points to the largest node.

Then we connect:

```text
head.left = prev
prev.right = head
```

This makes the list circular.

## Algorithm

Handle the empty tree first:

```python
if not root:
    return None
```

Initialize:

```python
head = None
prev = None
```

Run inorder DFS.

For each visited node:

If this is the first visited node:

```python
head = node
```

Otherwise, connect the previous node and current node:

```python
prev.right = node
node.left = prev
```

Then update:

```python
prev = node
```

After DFS finishes, close the circular list:

```python
head.left = prev
prev.right = head
```

Return:

```python
head
```

## Correctness

Inorder traversal of a BST visits nodes in ascending order.

During traversal, suppose the current node is `node`.

All nodes visited before `node` are smaller than or equal to `node`, and because we process nodes one by one in sorted order, `prev` is exactly the node that should come immediately before `node` in the final list.

When we execute:

```python
prev.right = node
node.left = prev
```

we create the correct successor and predecessor links between two adjacent nodes in sorted order.

The first visited node has no smaller predecessor, so we store it as `head`. In a BST, the first inorder node is the smallest node, so returning `head` satisfies the problem requirement.

After traversal ends, `prev` is the last visited node. In a BST, the last inorder node is the largest node. Connecting:

```python
head.left = prev
prev.right = head
```

adds the required circular links between the smallest and largest nodes.

Therefore, every node is linked to its sorted predecessor and successor, and the returned node is the smallest node.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Every node is visited once |
| Space | `O(h)` | Recursion stack height is the tree height |

Here, `n` is the number of nodes.

`h` is the height of the tree.

For a balanced BST, `h = O(log n)`.

For a completely skewed BST, `h = O(n)`.

## Implementation

```python
class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None

        self.head = None
        self.prev = None

        def inorder(node: 'Optional[Node]') -> None:
            if not node:
                return

            inorder(node.left)

            if self.prev:
                self.prev.right = node
                node.left = self.prev
            else:
                self.head = node

            self.prev = node

            inorder(node.right)

        inorder(root)

        self.head.left = self.prev
        self.prev.right = self.head

        return self.head
```

## Code Explanation

We first handle the empty tree:

```python
if not root:
    return None
```

An empty tree has no nodes to link, so the correct answer is `None`.

We keep two fields:

```python
self.head = None
self.prev = None
```

`self.head` stores the first node visited by inorder traversal.

`self.prev` stores the node visited immediately before the current node.

The DFS function follows inorder order:

```python
inorder(node.left)
...
inorder(node.right)
```

This is the important part. Since the input is a BST, inorder traversal gives the nodes in sorted order.

When we visit a node, there are two cases.

If `self.prev` already exists:

```python
self.prev.right = node
node.left = self.prev
```

This links the previous sorted node with the current sorted node.

If `self.prev` does not exist:

```python
self.head = node
```

This means we are visiting the smallest node, so it becomes the head of the list.

Then we move `self.prev` forward:

```python
self.prev = node
```

After DFS completes, `self.head` is the smallest node and `self.prev` is the largest node.

We close the circle:

```python
self.head.left = self.prev
self.prev.right = self.head
```

Finally, we return the smallest node:

```python
return self.head
```

## Testing

For local testing, we can build a small tree and walk through the circular list.

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

def list_forward(head, count):
    ans = []
    cur = head

    for _ in range(count):
        ans.append(cur.val)
        cur = cur.right

    return ans

def list_backward(head, count):
    ans = []
    cur = head.left

    for _ in range(count):
        ans.append(cur.val)
        cur = cur.left

    return ans

def run_tests():
    s = Solution()

    root = Node(
        4,
        Node(2, Node(1), Node(3)),
        Node(5),
    )

    head = s.treeToDoublyList(root)

    assert list_forward(head, 5) == [1, 2, 3, 4, 5]
    assert list_backward(head, 5) == [5, 4, 3, 2, 1]

    assert head.val == 1
    assert head.left.val == 5
    assert head.left.right == head

    single = Node(10)
    head = Solution().treeToDoublyList(single)

    assert head.val == 10
    assert head.left == head
    assert head.right == head

    assert Solution().treeToDoublyList(None) is None

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4,2,5,1,3]` | Checks normal BST conversion |
| Forward traversal | Confirms `right` links are correct |
| Backward traversal | Confirms `left` links are correct |
| Circular links | Confirms head and tail are connected |
| Single node | Checks self-circular case |
| Empty tree | Checks `None` input |