Log inSign up
mediumLeetCodeNot Started

BST to Sorted Doubly Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

Treat the left and right pointers of each tree node as prev and next pointers of a doubly-linked list: - The left pointer should point to its predecessor. - The right pointer should point to its successor. - For a circular doubly-linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

Return the pointer to the smallest element of the linked list.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Repurpose tree child pointers into doubly-linked list pointers in place.
  • Maintain running predecessor state across recursive inorder frames.
  • Close circular pointers cleanly after completing the tree traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Convert BST to Doubly Linked List in-place.
  • Reinterpret left/right pointers as prev/next.
  • Circular linked list closure requirement.

Algorithmic Decision Tree:

  • Maintain prev pointer during inorder DFS: link prev and curr.
  • Make circular after traversal: tail.right = head; head.left = tail.

Connected Patterns:

Flatten Binary Tree to Linked ListBinary Search Tree IteratorInorder Traversal

1. Inorder Array Collection

Intuition

Perform an inorder traversal to append all tree node references into a list. Then iterate from 0 to N - 1, setting nodes[i].right = nodes[(i + 1) % N] and nodes[i].left = nodes[(i - 1 + N) % N]. Return nodes[0].

When to apply: Simpler mental model when extra memory is allowed.

Algorithm

  1. Step 1: If root is null, return null.
  2. Step 2: Collect all nodes in inorder array nodes.
  3. Step 3: Loop i from 0 to N - 1: link nodes[i].right = nodes[(i + 1) % N] and nodes[i].left = nodes[(i - 1 + N) % N].
  4. Step 4: Return nodes[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct Node {
6 int val;
7 Node* left;
8 Node* right;
9 Node(int _val) : val(_val), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 void inorder(Node* root, vector<Node*>& nodes) {
14 if (!root) return;
15 inorder(root->left, nodes);
16 nodes.push_back(root);
17 inorder(root->right, nodes);
18 }
19public:
20 Node* treeToDoublyList(Node* root) {
21 if (!root) return nullptr;
22 vector<Node*> nodes;
23 inorder(root, nodes);
24 int n = nodes.size();
25 for (int i = 0; i < n; i++) {
26 nodes[i]->right = nodes[(i + 1) % n];
27 nodes[i]->left = nodes[(i - 1 + n) % n];
28 }
29 return nodes[0];
30 }
31};
32
33int main() {
34 Node* root = new Node(4);
35 root->left = new Node(2);
36 root->right = new Node(5);
37 Solution sol;
38 Node* head = sol.treeToDoublyList(root);
39 cout << "Head: " << head->val << ", Next: " << head->right->val << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Recursive Inorder with Running Prev Pointer (O(H) Space)

Intuition

Maintain two pointers: first (the head of the linked list) and prev (the predecessor node). During inorder traversal, if prev exists, link prev.right = curr and curr.left = prev. If first is null, set first = curr. Update prev = curr. After traversal, link first.left = prev and prev.right = first.

When to apply: Standard recursive in-place solution.

Algorithm

  1. Step 1: If root == null, return null.
  2. Step 2: Helper inorder(curr): recurse left.
  3. Step 3: If prev != null, link prev.right = curr and curr.left = prev. Else first = curr.
  4. Step 4: prev = curr. Recurse right.
  5. Step 5: After traversal: prev.right = first; first.left = prev. Return first.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2using namespace std;
3
4struct Node {
5 int val;
6 Node* left;
7 Node* right;
8 Node(int _val) : val(_val), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 Node* first = nullptr;
13 Node* prev = nullptr;
14 void inorder(Node* node) {
15 if (!node) return;
16 inorder(node->left);
17 if (prev) {
18 prev->right = node;
19 node->left = prev;
20 } else {
21 first = node;
22 }
23 prev = node;
24 inorder(node->right);
25 }
26public:
27 Node* treeToDoublyList(Node* root) {
28 if (!root) return nullptr;
29 inorder(root);
30 prev->right = first;
31 first->left = prev;
32 return first;
33 }
34};
35
36int main() {
37 Node* root = new Node(4);
38 root->left = new Node(2);
39 root->right = new Node(5);
40 Solution sol;
41 Node* head = sol.treeToDoublyList(root);
42 cout << "Optimal Head: " << head->val << ", Tail: " << head->left->val << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack

3. Morris Traversal In-Place Linking (O(1) Space)

Intuition

Using Morris Inorder Traversal, we find the inorder predecessor of each node and create temporary threads (pred.right = curr). When visiting the node, link it with prev and adjust pointers. This achieves O(N) runtime with strictly O(1) auxiliary memory.

When to apply: When strictly O(1) auxiliary space is required.

Algorithm

  1. Step 1: Initialize curr = root, first = null, prev = null.
  2. Step 2: If curr.left == null: process curr, link with prev, move curr = curr.right.
  3. Step 3: Else find rightmost node of curr.left (pred).
  4. Step 4: If pred.right == null: pred.right = curr, curr = curr.left.
  5. Step 5: Else: process curr, link with prev, curr = curr.right.
  6. Step 6: At end, connect prev.right = first; first.left = prev. Return first.

BST to Doubly Linked List Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Tree root 4 has left child 2 and right child 5
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Step 1
Why this step matters

Tree root 4 has left child 2 and right child 5.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2using namespace std;
3
4struct Node {
5 int val;
6 Node* left;
7 Node* right;
8 Node(int _val) : val(_val), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13 Node* treeToDoublyList(Node* root) {
14 if (!root) return nullptr;
15 Node* first = nullptr;
16 Node* prev = nullptr;
17 Node* curr = root;
18 while (curr) {
19 if (!curr->left) {
20 if (prev) { prev->right = curr; curr->left = prev; }
21 else first = curr;
22 prev = curr;
23 curr = curr->right;
24 } else {
25 Node* pred = curr->left;
26 while (pred->right && pred->right != curr) pred = pred->right;
27 if (!pred->right) {
28 pred->right = curr;
29 curr = curr->left;
30 } else {
31 if (prev) { prev->right = curr; curr->left = prev; }
32 else first = curr;
33 prev = curr;
34 curr = curr->right;
35 }
36 }
37 }
38 prev->right = first;
39 first->left = prev;
40 return first;
41 }
42};
43
44int main() {
45 Node* root = new Node(4);
46 root->left = new Node(2);
47 root->right = new Node(5);
48 Solution sol;
49 Node* head = sol.treeToDoublyList(root);
50 cout << "Morris Head: " << head->val << ", Tail: " << head->left->val << endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Inorder ArrayO(N)O(N)Collect nodes in array, link in loop.Array memory allocation.
2.Recursive Inorder with PrevO(N)O(H)Link on-the-fly during DFS.Call stack depth.
3.Morris Traversal (Optimal)OptimalO(N)O(1)Threaded binary tree linking without stack.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Modifying `curr.right` before exploring it

If you update curr.right before visiting curr.right, you lose the pointer to the right subtree. Inorder DFS safely explores curr.right after updating prev.

Forgetting to close the circular loop

Failing to connect tail.right = head and head.left = tail leaves the list open.

Not guarding root == null

Attempting first.left = prev when tree is empty causes a null pointer crash.

Crucial Edge Cases to Validate:

  • Empty tree (root == null) — Must return null without throwing errors.
  • Single node tree — A single node's left and right pointers must both point to itself (root.left = root; root.right = root).
  • Skewed BST (linked list) — In-place pointer modifications handle extreme trees without cycles.
  • Two-node tree — Correctly forms a 2-node circular doubly linked list.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the key realization: 'Inorder visits nodes in strictly sorted order. Overwriting curr.left is safe because the left subtree has already been processed.'
  2. Point out how prev and first pointers mirror doubly-linked list construction.
  3. Mention that Morris traversal eliminates the O(H) recursion stack for systems with strict memory constraints.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the recursive inorder traversal with a previous pointer work without modifying future unvisited subtrees?

2.How is the list made circular after the traversal completes?

3.What is the return value of treeToDoublyList when the input root is null?

Back to DSA Sheet