Full lesson preview

Convert a BST to a sorted doubly linked list

Transform a binary search tree into a sorted doubly linked list (in-order) in-place, returning the head.

Python practice32 minTrees & Binary TreesAdvancedLast updated March 29, 2026

Problem statement

Given the root of a binary search tree (BST), convert it into a sorted doubly linked list in-place. The left pointer of each node should be used as the previous pointer, and the right pointer as the next pointer. Return the head of the resulting doubly linked list (the smallest element). Do not create new node objects; rearrange pointers of existing nodes. Aim for O(n) time and O(h) recursion space.

Task

Perform an in-place conversion of a BST to a doubly linked list using O(n) time and O(h) recursion space, preserving node objects and using left as prev and right as next.

Examples

Small BST

Input

TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(5))

Output

[1, 2, 3, 4, 5]

In-order traversal of the BST yields sorted order; return list of node values by traversing next pointers from head.

Input format

A single binary search tree root (TreeNode or None).

Output format

A doubly linked list head (TreeNode) — for tests we will convert it to a Python list of values by following right pointers and return that list.

Constraints

Number of nodes up to 10^5. Must be in-place, O(n) time, O(h) recursion space.

Samples

Sample 1

Input

TreeNode(1)

Output

[1]

A single-node tree becomes a one-element doubly linked list.