426. Convert BST to Sorted Doubly Linked List

426

MediumTrees and Binary Search TreesBST inorder traversal building a circular doubly linked listInorder traversal linking prev to current

Convert BST to Sorted Doubly Linked List

Convert a binary search tree in place into a sorted circular doubly linked list, where left acts as the predecessor pointer and right as the successor pointer. Return a pointer to the smallest element; the list's ends wrap around to each other.

Open official problem prompt ↗

In plain English

Rewire a BST's existing nodes into a sorted, circular, doubly linked list without allocating new nodes.

Picture it like this

Walking a sorted bookshelf left to right and clipping each book to the one you just passed, then joining the last book back to the first to form a carousel.

Example

Input: root = [4,2,5,1,3]
Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 (circular)
Why: Inorder order of the BST is 1,2,3,4,5; each node links to its sorted neighbors and 5 wraps back to 1.

Constraints

The number of nodes is in the range [0, 2000]-1000 <= Node.val <= 1000All values are unique

Pattern lesson

See the pattern, then code

Inorder traversal linking prev to current

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. An inorder walk visits nodes in ascending order, so keep a pointer to the previously visited node and, at each node, connect prev.right to it and its left to prev; finally close the ring between the first and last.

New words, made simpleKnow these before the algorithm

Doubly linked list: A list where each node points to both its predecessor and successor.
Circular list: The last node links to the first and the first links back to the last.
Predecessor pointer: Here the reused left pointer, storing the previous (smaller) node.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Inorder into an array then relink

Works but stores an extra array of all nodes.

Collect nodes in sorted order, then loop to set left/right pointers.

Time O(n)Space O(n)

Best choiceIn-place inorder with a prev pointer

One traversal, only recursion stack, links built as you go.

Link each node to the previously visited one during a single inorder pass.

Time O(n)Space O(h)

The rule we keep true

Invariant

When a node is visited, last points to the largest value seen so far, so linking node to last extends a correctly sorted chain.

Why this is correct

Reasoning

Inorder traversal of a BST yields strictly increasing values. Linking each visited node to its immediate predecessor builds the sorted chain incrementally; the very first visit sets the head, and closing last-to-first after the walk produces the circular structure.

The algorithm in three movesSay these aloud before coding

1Track first (smallest) and last (previously visited) nodes

visit 1 -> first=1, last=1

2Inorder: recurse left, process node, recurse right

visit 2 -> 1.right=2, 2.left=1

3At each node, link last.right to it and its left to last, or record it as first

close: 5.right=1, 1.left=5

4After traversal, connect last and first to make the list circular

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readleftmost node

2 · AskAny prev?

3 · Update statelast=None -> first=1

4 · Resultfirst=1, last=1

Key takeaway

Nodes wired in sorted order 1..5 with the ends (5 and 1) joined into a ring.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Empty guard
An empty tree becomes an empty list (None).
2
Lines 5-6Track ends
first will be the head; last is the previously visited node.
3
Lines 7-18Inorder link
Recurse left, wire the node to last (or set first), advance last, then recurse right.
4
Lines 20-22Make circular
After the walk, join last and first so the ends wrap around; return the smallest.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty tree returns None
Single node links to itself in both directions
Left- or right-skewed tree still linearizes in sorted order

Common beginner mistakes

Forgetting to close the ring, leaving a plain (non-circular) list
Overwriting left/right before reading the child, corrupting traversal (recurse into children before rewiring)
Losing the head pointer by only tracking the previous node

Check your understanding

Why must the left and right children be visited before (or captured before) rewiring a node's pointers?

PyPython 3 · solution.py

Optimal

1class Solution:2    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':3        if not root:4            return None5        self.first = None6        self.last = None7        def inorder(node):8            if not node:9                return10            inorder(node.left)11            if self.last:12                self.last.right = node13                node.left = self.last14            else:15                self.first = node16            self.last = node17            inorder(node.right)18        inorder(root)19        self.last.right = self.first20        self.first.left = self.last21        return self.first

Time complexityO(n)Optimized

Space complexityO(h)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaAmazonMicrosoft

Convert BST to Sorted Doubly Linked List

Convert BST to Sorted Doubly Linked List

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees