LeetCode 426 - Convert Binary Search Tree to Sorted Doubly Linked List

LeetCode Problem 426

Difficulty: 🟡 Medium
Topics: Linked List, Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree, Doubly-Linked List

Solution

Problem Understanding

The problem asks us to transform a Binary Search Tree, abbreviated as BST, into a sorted circular doubly linked list. The transformation must happen in place, meaning we are not allowed to create entirely new nodes for the linked list. Instead, we reuse the existing tree nodes and reinterpret their left and right pointers as doubly linked list pointers.

In a doubly linked list, every node has two directional connections:

• One pointer to the previous node
• One pointer to the next node

In this problem:

• left becomes the predecessor pointer
• right becomes the successor pointer

The list must also be circular. That means:

• The smallest node's predecessor points to the largest node
• The largest node's successor points back to the smallest node

The input is the root of a Binary Search Tree. A BST has the important property that:

• Every value in the left subtree is smaller than the current node
• Every value in the right subtree is larger than the current node

Because of this property, an inorder traversal of the BST visits nodes in sorted order. This observation is the key to solving the problem efficiently.

The expected output is the head of the circular doubly linked list, specifically the smallest node in sorted order.

The constraints tell us that the tree can contain up to 2000 nodes. This is small enough that even less optimal approaches could pass, but the problem explicitly asks for an in-place transformation, so we should aim for a solution that reuses the tree structure efficiently.

Several edge cases are important:

• The tree may be empty, in which case we should return None
• The tree may contain only one node, which should point to itself in both directions
• The tree may be heavily skewed, making recursion depth an important consideration
• The BST property guarantees unique values, so we never need to handle duplicates

Approaches

Brute Force Approach

A straightforward solution is to perform an inorder traversal of the BST and store all visited nodes in an array or list. Since inorder traversal of a BST produces values in sorted order, the array will contain nodes in the exact order needed for the doubly linked list.

After collecting all nodes, we iterate through the array and manually connect neighboring nodes:

• nodes[i].right = nodes[i + 1]
• nodes[i + 1].left = nodes[i]

Finally, we connect the first and last nodes to make the list circular.

This approach is correct because inorder traversal guarantees sorted ordering in a BST. However, it uses additional memory proportional to the number of nodes because every node reference is stored in the auxiliary list.

Optimal Approach

The key insight is that we do not actually need an intermediate array.

Since inorder traversal already visits nodes in sorted order, we can connect nodes immediately as we traverse the tree. We maintain two pointers during traversal:

• prev, the previously visited node
• head, the smallest node encountered so far

As we visit each node:

• We connect prev.right to the current node
• We connect current.left to prev

This incrementally builds the doubly linked list in sorted order.

After traversal completes:

• head points to the smallest node
• prev points to the largest node

We then connect them together to make the list circular.

This solution is optimal because it performs the conversion in place and avoids storing all nodes separately.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses inorder traversal plus an auxiliary array of nodes
Optimal	O(n)	O(h)	Builds the list during traversal, recursion stack depends on tree height

Algorithm Walkthrough

1. Handle the empty tree case immediately.

If the root is None, there is no linked list to build, so we return None. 2. Initialize two pointers, head and prev.

head will eventually point to the smallest node in the BST, which becomes the head of the linked list.

prev tracks the previously processed node during inorder traversal. This allows us to connect adjacent nodes in sorted order. 3. Perform an inorder traversal of the BST.

Inorder traversal visits nodes in this order:

• Left subtree
• Current node
• Right subtree

Because the tree is a BST, this traversal naturally visits nodes in ascending sorted order. 4. Process the current node during traversal.

When visiting a node:

• If prev exists, connect:

• prev.right = current

• current.left = prev

This links the current node with the previously visited node.

• If prev does not exist, this is the first node visited, meaning it is the smallest node in the BST. Set head = current.

5. Update prev.

After processing the current node, assign:

prev = current

This prepares for linking the next visited node. 6. Continue traversal into the right subtree.

The inorder traversal continues recursively, preserving sorted ordering. 7. Make the list circular after traversal completes.

At the end:

• head points to the smallest node
• prev points to the largest node

Connect them together:

• head.left = prev
• prev.right = head

8. Return head.

This is the required output pointer.

Why it works

The correctness comes from the BST inorder traversal property. Inorder traversal always visits BST nodes in ascending sorted order. By linking each node to the previously visited node during traversal, we construct a correctly ordered doubly linked list incrementally. The final step connects the smallest and largest nodes, making the structure circular without breaking sorted ordering.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""

from typing import Optional

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

The implementation begins by handling the empty tree case. If root is None, the function immediately returns None.

Two instance variables are then initialized:

• self.head stores the smallest node
• self.prev stores the previously visited node during traversal

The nested inorder function performs the recursive inorder traversal.

The traversal first processes the left subtree, ensuring smaller values are visited before the current node. When the current node is processed:

• If self.prev exists, the current node is linked to the previous node
• Otherwise, the current node is the smallest node, so it becomes the head

After processing, self.prev is updated to the current node so the next visited node can connect back to it.

Once traversal finishes, the list is almost complete but still linear. The final two assignments connect the head and tail together to make the structure circular.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 * }
 */

func treeToDoublyList(root *Node) *Node {
    if root == nil {
        return nil
    }

    var head *Node
    var prev *Node

    var inorder func(*Node)

    inorder = func(node *Node) {
        if node == nil {
            return
        }

        inorder(node.Left)

        if prev != nil {
            prev.Right = node
            node.Left = prev
        } else {
            head = node
        }

        prev = node

        inorder(node.Right)
    }

    inorder(root)

    head.Left = prev
    prev.Right = head

    return head
}

The Go implementation follows the same logical structure as the Python version. The main difference is that Go uses explicit pointer handling instead of Python references.

Go uses nil instead of None, and recursive helper functions are declared using function variables so they can recursively reference themselves.

Because Go does not support nested function closures with implicit object state like Python classes do, head and prev are captured by the recursive closure.

Worked Examples

Example 1

Input BST:

        4
       / \
      2   5
     / \
    1   3

Inorder traversal order:

1 → 2 → 3 → 4 → 5

Traversal state:

Current Node	prev Before	Action	head	prev After
1	None	Set head = 1	1	1
2	1	Link 1 ↔ 2	1	2
3	2	Link 2 ↔ 3	1	3
4	3	Link 3 ↔ 4	1	4
5	4	Link 4 ↔ 5	1	5

After traversal:

• head = 1
• prev = 5

Circular connections:

1.left = 5
5.right = 1

Final circular doubly linked list:

1 ↔ 2 ↔ 3 ↔ 4 ↔ 5
↑                 ↓
└─────────────────┘

Example 2

Input BST:

    2
   / \
  1   3

Inorder traversal order:

1 → 2 → 3

Traversal state:

Current Node	prev Before	Action	head	prev After
1	None	Set head = 1	1	1
2	1	Link 1 ↔ 2	1	2
3	2	Link 2 ↔ 3	1	3

Final circular connections:

1.left = 3
3.right = 1

Final list:

1 ↔ 2 ↔ 3
↑         ↓
└─────────┘

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack stores at most tree height frames

The algorithm processes each node exactly one time during inorder traversal, giving linear time complexity.

The extra space comes only from recursion. In a balanced BST, the height is O(log n), while in the worst case of a skewed tree, the height becomes O(n).

Test Cases

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

def circular_list_values(head, count):
    result = []
    current = head

    for _ in range(count):
        result.append(current.val)
        current = current.right

    return result

# Example 1
root1 = Node(4)
root1.left = Node(2)
root1.right = Node(5)
root1.left.left = Node(1)
root1.left.right = Node(3)

head1 = Solution().treeToDoublyList(root1)
assert circular_list_values(head1, 5) == [1, 2, 3, 4, 5]  # standard BST conversion

# Example 2
root2 = Node(2)
root2.left = Node(1)
root2.right = Node(3)

head2 = Solution().treeToDoublyList(root2)
assert circular_list_values(head2, 3) == [1, 2, 3]  # small balanced tree

# Empty tree
head3 = Solution().treeToDoublyList(None)
assert head3 is None  # empty input

# Single node tree
root4 = Node(10)

head4 = Solution().treeToDoublyList(root4)
assert head4.val == 10  # single node value
assert head4.left == head4  # circular predecessor
assert head4.right == head4  # circular successor

# Left-skewed tree
root5 = Node(4)
root5.left = Node(3)
root5.left.left = Node(2)
root5.left.left.left = Node(1)

head5 = Solution().treeToDoublyList(root5)
assert circular_list_values(head5, 4) == [1, 2, 3, 4]  # descending insertion order

# Right-skewed tree
root6 = Node(1)
root6.right = Node(2)
root6.right.right = Node(3)
root6.right.right.right = Node(4)

head6 = Solution().treeToDoublyList(root6)
assert circular_list_values(head6, 4) == [1, 2, 3, 4]  # ascending chain

# Verify circularity explicitly
assert head1.left.val == 5  # head predecessor is tail
assert head1.left.right == head1  # tail points back to head

Test	Why
Balanced BST [4,2,5,1,3]	Verifies standard inorder conversion
Small BST [2,1,3]	Confirms basic linking logic
Empty tree	Ensures None handling works
Single node tree	Verifies self-referential circular links
Left-skewed tree	Tests worst-case recursion direction
Right-skewed tree	Tests opposite skew direction
Explicit circularity check	Ensures head and tail connect correctly

Edge Cases

Empty Tree

An empty tree is represented by root = None. This case is important because recursive traversal assumes nodes exist. Without an early return, the implementation could attempt invalid pointer operations.

The solution handles this immediately at the start:

if not root:
    return None

This guarantees no traversal occurs for empty input.

Single Node Tree

A BST containing only one node is a subtle edge case because the node must point to itself in both directions.

For example:

1

The resulting circular doubly linked list should satisfy:

1.left = 1
1.right = 1

The implementation handles this naturally because:

• The single node becomes both head and prev
• The final circular linking step connects the node back to itself

Skewed Trees

A skewed BST behaves like a linked list rather than a balanced tree.

Example:

1
 \
  2
   \
    3

This case matters because recursion depth becomes O(n) instead of O(log n). Incorrect traversal ordering or pointer updates can easily produce broken links.

The inorder traversal still processes nodes in sorted order, and the algorithm maintains correctness because each node is linked only after its predecessor has already been processed.