How to convert a tree to a doubly linked list in C++?

Introduction

Converting a binary tree or binary search tree (BST) into a doubly linked list (DLL) is a standard programming and interview problem. In this process, we reuse the tree’s left and right pointers: the left becomes the prev pointer, and the right becomes the next pointer in the doubly linked list. The order of elements in the final list typically follows an inorder traversal (i.e., left → root → right).

Why is this useful?

It helps practice tree-pointer manipulations and in-place transformations.
Many problems (on coding platforms, interviews in India or elsewhere) ask for “BST to sorted doubly linked list in C++” or “convert binary tree to DLL in place.”
It shows how a hierarchical structure (tree) can be flattened into a linear two-way structure (DLL).

Problem Statement - What exactly do we want

Let’s restate in plain words:

Input: A binary tree node root (possibly a BST).
Output: A doubly linked list, whose nodes are the same tree nodes, linked in inorder sequence.
Mapping: For each node:
- node->left will act as prev in DLL
- node->right will act as next in DLL
The leftmost node (smallest in inorder) becomes the head of the DLL, with its left = nullptr.
The rightmost node’s right = nullptr (if not making it circular).
This conversion must be in-place, i.e. no new nodes allocated (we reuse original tree nodes).

So the goal is: “convert binary tree to doubly linked list in C++ in place”, preserving inorder order.

Core idea — Why inorder traversal helps

When you traverse a binary tree in inorder (left, root, right), you exactly visit nodes in the order you want in the final doubly linked list. So the strategy is:

Traverse the left subtree
Visit the current node → link it with the previously visited node
Traverse the right subtree

We maintain a pointer prev that always points to the last node we processed in the DLL. When we reach a new node curr, we do:

prev->right = curr
curr->left = prev

If prev is nullptr (i.e. first visited node), we mark this curr as the head of the DLL.

Thus, as we traverse, we gradually “chain” nodes into a doubly linked list.

This is the standard method explained in many algorithm resources.

Main approaches (with pros & cons)

Here are three common ways to implement tree → DLL conversion in C++:

1. Recursive Inorder Approach (simplest)

How it works

Use recursion to do an in-order traversal
Use prev and head pointers as described above
At each visit, link prev <-> curr

Time & Space

Time: O(n) — each node visited once
Space: O(h) due to recursion stack, where h = tree height (in worst case, h = n)

Full C++ code example

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* prevPtr = nullptr;  // tracks last processed node
Node* headDLL = nullptr;  // head of final doubly linked list

void inorderConvert(Node* root) {
    if (root == nullptr) return;
    inorderConvert(root->left);

    // now “visit” this node
    if (prevPtr == nullptr) {
        // this is the first (leftmost) node
        headDLL = root;
    } else {
        prevPtr->right = root;
        root->left = prevPtr;
    }
    prevPtr = root;

    inorderConvert(root->right);
}

void printDLL(Node* head) {
    Node* cur = head;
    while (cur) {
        cout << cur->val;
        if (cur->right) cout << " <-> ";
        cur = cur->right;
    }
    cout << "\n";
}

int main() {
    // Example tree:
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(20);
    root->right->left = new Node(15);

    inorderConvert(root);
    printDLL(headDLL);
    // Output: 5 <-> 10 <-> 15 <-> 20

    return 0;
}

Why this approach is good

Very easy to understand
Direct mapping from idea → code
Suitable for many interview/practice problems

Limitations

Deep recursion may cause a stack overflow if the tree is extremely skewed
Extra recursion overhead

2. Iterative Approach (using explicit stack)

Idea

Simulate the recursion yourself using a stack
Same linking logic with prev pointer
This avoids deep recursion and gives you explicit control

Pseudo/sketch

Create an empty stack
Use a pointer curr = root
While (curr != nullptr or stack not empty):
a. Go deep: while curr != nullptr, push curr and move curr = curr->left
b. Pop node from stack → call it node
c. Visit/link it: prev->right = node, node->left = prev, etc.
d. Set prev = node
e. Move curr = node->right

Pros & cons

Pros: avoids recursion, safer for deep trees
Cons: slightly more code, you must manage the stack and pointers carefully

I can provide a full C++ version on request.

3. Morris Traversal / Threaded Approach (O(1) extra space)

Idea

Use Morris inorder traversal technique to avoid recursion and stack
Temporarily create “threads” (right pointers) in the tree to revisit nodes
When you “visit” a node in the Morris scheme, do the linking to the DLL.

High-level sketch

Node* curr = root;
Node* prev = nullptr;
Node* head = nullptr;

while (curr) {
    if (curr->left == nullptr) {
        // visit curr
        if (!prev) head = curr;
        else {
            prev->right = curr;
            curr->left = prev;
        }
        prev = curr;
        curr = curr->right;
    } else {
        Node* pred = curr->left;
        while (pred->right && pred->right != curr) {
            pred = pred->right;
        }
        if (pred->right == nullptr) {
            pred->right = curr;  // make thread
            curr = curr->left;
        } else {
            pred->right = nullptr;  // remove thread
            // visit curr
            if (!prev) head = curr;
            else {
                prev->right = curr;
                curr->left = prev;
            }
            prev = curr;
            curr = curr->right;
        }
    }
}

Pros & cons

Pros: O(1) extra memory (apart from pointers)
Cons: more delicate, risk of pointer mistakes, harder to debug

Use Morris only when memory is strictly constrained and you are comfortable with manipulating tree pointers.

Which method to choose (for everyday coding)

For clarity, readability, and interview ease: Recursive method is best.
For deeper trees or systems with limited recursion depth: prefer the iterative stack method.
For minimal additional memory usage: use Morris traversal, but only if you’re confident.

Edge Cases, Pitfalls & Debugging Tips

Empty tree (root = nullptr) → result head = nullptr.
Single node tree → DLL with one node; left = right = nullptr.
Skewed tree (like a linked list) → recursion depth = n; use iterative variant.
Always check you set both prev->right = curr and curr->left = prev — missing one breaks the links.
If asked for a circular DLL, after conversion, link the tail to head:
tail->right = head; head->left = tail;
In Morris method, be careful to restore modified pointers (remove threads) so the original tree structure is not broken.

Full Example - Recursive + Iterative (combined)

Below is a combined C++ program that includes both recursive and iterative versions, so you can test both:

#include <iostream>
#include <stack>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

// ============ Recursive method ============
Node* recPrev = nullptr;
Node* recHead = nullptr;

void inorderRec(Node* root) {
    if (!root) return;
    inorderRec(root->left);
    if (!recPrev) {
        recHead = root;
    } else {
        recPrev->right = root;
        root->left = recPrev;
    }
    recPrev = root;
    inorderRec(root->right);
}

// ============ Iterative method ============
Node* convertIterative(Node* root) {
    if (!root) return nullptr;
    stack<Node*> st;
    Node* curr = root;
    Node* prev = nullptr;
    Node* head = nullptr;

    while (curr || !st.empty()) {
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top();
        st.pop();
        if (!prev) {
            head = curr;
        } else {
            prev->right = curr;
            curr->left = prev;
        }
        prev = curr;
        curr = curr->right;
    }
    return head;
}

// Print DLL
void printDLL(Node* head) {
    Node* cur = head;
    while (cur) {
        cout << cur->val;
        if (cur->right) cout << " <-> ";
        cur = cur->right;
    }
    cout << "\n";
}

int main() {
    // Example tree
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(20);
    root->right->left = new Node(15);

    // Recursive version
    inorderRec(root);
    cout << "Recursive conversion gives: ";
    printDLL(recHead);

    // Reset globals (not strictly necessary for this example)
    recPrev = nullptr; recHead = nullptr;

    // Iterative version
    Node* head2 = convertIterative(root);
    cout << "Iterative conversion gives: ";
    printDLL(head2);

    return 0;
}

Summary

Converting a binary tree (or BST) to a doubly linked list in C++ means reusing left / right pointers as prev / next.
The inorder traversal order is the natural order for conversion.
You have three main approaches: recursive, iterative (stack), and Morris (constant extra space).
Use the recursive method for simplicity, iterative if recursion depth is a concern, and Morris when you need minimal memory overhead.
Always handle edge cases and carefully maintain pointer links.