Convert Binary Search Tree to Sorted Doubly Linked List

medium tree dfs linked list

Problem

Convert a Binary Search Tree to a sorted circular doubly-linked list in place — the left pointer becomes prev and the right pointer becomes next.

Inputroot = [4,2,5,1,3]

Output1↔2↔3↔4↔5↔1

In-order traversal: 1,2,3,4,5 — links each to the next and wraps tail↔head.

BST (level-order, 'n' for null)

def tree_to_doubly_list(root):
    if not root: return None
    first = last = None
    def inorder(node):
        nonlocal first, last
        if not node: return
        inorder(node.left)
        if last: last.right = node; node.left = last
        else: first = node
        last = node
        inorder(node.right)
    inorder(root)
    first.left = last; last.right = first
    return first

function treeToDoublyList(root) {
  if (!root) return null;
  let first = null, last = null;
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    if (last) { last.right = node; node.left = last; } else first = node;
    last = node;
    inorder(node.right);
  }
  inorder(root);
  first.left = last; last.right = first;
  return first;
}

class Solution {
    Node first, last;
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        inorder(root);
        first.left = last; last.right = first;
        return first;
    }
    void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        if (last != null) { last.right = node; node.left = last; } else first = node;
        last = node;
        inorder(node.right);
    }
}

class Solution {
    Node *first = nullptr, *last = nullptr;
    void inorder(Node* node) {
        if (!node) return;
        inorder(node->left);
        if (last) { last->right = node; node->left = last; } else first = node;
        last = node;
        inorder(node->right);
    }
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        inorder(root);
        first->left = last; last->right = first;
        return first;
    }
};

Explanation

We flatten a BST into a sorted circular doubly linked list in place. The key insight is that an in-order traversal of a BST visits nodes in increasing order, which is exactly the order the list should have.

As we walk in-order we keep a pointer last to the node we visited just before. When we reach a new node, we wire it to last: last.right = node (next) and node.left = last (prev). The very first node we ever reach has no predecessor, so we record it as first.

After the whole traversal, first is the smallest value and last is the largest. To make the list circular we connect the two ends: first.left = last and last.right = first.

Example: BST [4, 2, 5, 1, 3]. In-order gives 1, 2, 3, 4, 5; each gets linked to the previous one, then the ends wrap so you can go 5 → 1 and back 1 → 5.

This reuses the tree's own left/right pointers as prev/next, so no extra structures are needed and each node is touched once.

Time: O(n) Space: O(h)