Convert Binary Search Tree to Sorted Doubly Linked List

Convert Binary Search Tree to Sorted Doubly Linked List - Problem

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

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. 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.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Input & Output

Example 1 — Basic BST

$ Input: root = [4,2,5,1,3]

› Output: [1,2,3,4,5]

💡 Note: In-order traversal gives sorted sequence 1→2→3→4→5. Convert to circular doubly linked list where each node's left points to predecessor and right to successor.

Example 2 — Right-skewed Tree

$ Input: root = [2,1,3]

› Output: [1,2,3]

💡 Note: Simple BST with three nodes. In-order gives 1→2→3, converted to circular list.

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Single node becomes circular list pointing to itself: left and right both point to the same node.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary Search Tree with nodes [4,2,5,1,3]

In-Order Traversal

Visit nodes in sorted order: 1→2→3→4→5

Circular List

Connect as circular doubly linked list

Key Takeaway

🎯 Key Insight: In-order traversal of BST gives sorted sequence - connect nodes during traversal for optimal space

Asked in

G Google 45 f Facebook 38 M Microsoft 32 a Amazon 28

The key insight is that in-order traversal of a BST naturally gives nodes in sorted order. We can either collect nodes first then link them (O(n) space), or link them directly during traversal (O(h) space). Best approach uses in-order DFS with direct linking: Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass with Array Storage	O(n)	O(n)	Store all nodes in array via in-order traversal, then rebuild links
In-Order DFS with Direct Linking	O(n)	O(h)	Connect nodes directly during in-order traversal without extra storage

Two-Pass with Array Storage — Algorithm Steps

Step 1: In-order traverse BST and store nodes in array
Step 2: Iterate through array and link each node to previous/next
Step 3: Connect first and last nodes to make it circular

Visualization

Tap to expand

Step-by-Step Walkthrough

In-order Traversal

Visit nodes: 1→2→3→4→5

Store in Array

Array: [1,2,3,4,5]

Link Circularly

Connect each node to prev/next, last to first

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorder(struct TreeNode* node, struct TreeNode** nodes, int* count) {
    if (node) {
        inorder(node->left, nodes, count);
        nodes[(*count)++] = node;
        inorder(node->right, nodes, count);
    }
}

struct TreeNode* solution(struct TreeNode* root) {
    if (!root) return NULL;
    
    struct TreeNode* nodes[1000];
    int count = 0;
    inorder(root, nodes, &count);
    
    for (int i = 0; i < count; i++) {
        int prevIdx = (i - 1 + count) % count;
        int nextIdx = (i + 1) % count;
        nodes[i]->left = nodes[prevIdx];
        nodes[i]->right = nodes[nextIdx];
    }
    
    return nodes[0];
}

int main() {
    // For simplicity, create a basic test case
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    
    struct TreeNode* result = solution(root);
    
    // Print circular list
    printf("[");
    struct TreeNode* current = result;
    int first = 1;
    do {
        if (!first) printf(",");
        printf("%d", current->val);
        current = current->right;
        first = 0;
    } while (current != result);
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes: O(n) for in-order traversal + O(n) for linking nodes

✓ Linear Growth

Space Complexity

O(n)

Array stores all n nodes plus O(h) recursion stack

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass with Array Storage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler