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:

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

The list must also be circular:

For example, if the BST contains values:

[1, 2, 3, 4, 5]

then the final doubly linked list should be:

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

and also circular:

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

The node definition is usually given as:

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

Examples

Consider this BST:

        4
       / \
      2   5
     / \
    1   3

The inorder order is:

1, 2, 3, 4, 5

So the converted list should be:

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

Because the list is circular:

1.left  = 5
5.right = 1

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

For a single-node tree:

1

The result is a circular list with one node:

1.right = 1
1.left  = 1

For an empty tree:

root = None

we return:

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:

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

we link:

1.right = 2
2.left  = 1

2.right = 3
3.left  = 2

...

Then make the list circular:

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:

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:

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:

head.left = prev
prev.right = head

This makes the list circular.

Algorithm

Handle the empty tree first:

if not root:
    return None

Initialize:

head = None
prev = None

Run inorder DFS.

For each visited node:

If this is the first visited node:

head = node

Otherwise, connect the previous node and current node:

prev.right = node
node.left = prev

Then update:

prev = node

After DFS finishes, close the circular list:

head.left = prev
prev.right = head

Return:

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:

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:

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

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

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:

if not root:
    return None

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

We keep two fields:

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:

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:

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:

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:

self.prev = node

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

We close the circle:

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

Finally, we return the smallest node:

return self.head

Testing

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

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: