Convert a Binary Tree into a Doubly Linked List - Visualization

Binary Trees

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given a binary tree, convert it into a doubly linked list (DLL) in-place. The nodes should be arranged in the same order as an in-order traversal of the binary tree. Each node's left pointer should point to the previous node in the DLL, and the right pointer should point to the next node.

Examples❯

Input Tree Level Order Output Description
[10, 12, 15, 25, 30, 36]
[[10], [12, 15], [25, 30, 36]] Standard binary tree; in-order traversal yields DLL: 25 ⇄ 12 ⇄ 30 ⇄ 10 ⇄ 36 ⇄ 15
[1]
[[1]] Single-node tree; DLL is just: 1
[] [] Empty tree; DLL does not exist
[4, 3, null, 2, null, 1]
[[4], [3], [2], [1]] Left-skewed tree; DLL follows in-order: 1 ⇄ 2 ⇄ 3 ⇄ 4
[5, null, 6, null, 7, null, 8]
[[5], [6], [7], [8]] Right-skewed tree; DLL is 5 ⇄ 6 ⇄ 7 ⇄ 8

Solution❯

Understanding the Problem

We are given a binary tree and our task is to convert it into a doubly linked list (DLL). The conversion must follow the in-order traversal sequence of the binary tree — that is, we must visit the left subtree, then the root, and finally the right subtree.

Each node in the tree contains a value, a left pointer, and a right pointer. In the DLL, the left pointer will act as the "previous" pointer, and the right pointer will act as the "next" pointer.

This transformation is done *in-place*, meaning we won't use extra data structures for creating new nodes — we'll just adjust the pointers of existing nodes to form the DLL.

Step-by-Step Solution with Example

Step 1: Understand In-Order Traversal

In in-order traversal, we recursively visit the left subtree, then the current node, and finally the right subtree. This ensures nodes are visited in ascending order for a Binary Search Tree (BST).

Step 2: Use a Previous Pointer

While traversing the tree in-order, we maintain a pointer to the previously visited node. We connect the previous node's right pointer to the current node, and the current node's left pointer to the previous node.

Step 3: Maintain Head of DLL

The first node visited in in-order becomes the head of the resulting DLL. This node has no left pointer (i.e., left = null).

Step 4: Apply It on an Example

Let's say our binary tree is:

        10
       /        5    15

In-order traversal of this tree gives: 5 → 10 → 15

During traversal:

  • Visit 5: it becomes the head of DLL.
  • Visit 10: link 5.right = 10 and 10.left = 5.
  • Visit 15: link 10.right = 15 and 15.left = 10.

The final doubly linked list: 5 <-> 10 <-> 15

Edge Cases

Case 1: Empty Tree

If the input tree is null, there's nothing to convert. The output should also be null.

Case 2: Single Node Tree

For a tree with one node like [10], that node itself becomes the doubly linked list. Both its left and right pointers will remain null.

Result: 10

Case 3: Right Skewed Tree

Each node has only a right child: [10, null, 20, null, 30]

In-order traversal: 10 → 20 → 30

DLL: 10 <-> 20 <-> 30

Case 4: Left Skewed Tree

Each node has only a left child: [30, 20, null, 10, null]

In-order traversal: 10 → 20 → 30

DLL: 10 <-> 20 <-> 30

Case 5: Tree with Mixed Structure

Even in trees with a mix of left and right children, the same logic applies — we traverse in in-order and link accordingly. The DLL will reflect the in-order sequence.

Finally

This problem is a classic example of using in-order traversal with pointer adjustments to transform a tree structure into a linear one (DLL). For beginners, it reinforces the importance of traversal techniques, pointer manipulation, and understanding recursive logic.

Always remember to handle edge cases like empty trees or single-node trees gracefully, and ensure your recursive base case is well-defined to prevent stack overflow.

Algorithm Steps❯

  1. If the binary tree is empty, return null.
  2. Recursively convert the left subtree into a doubly linked list.
  3. Recursively convert the right subtree into a doubly linked list.
  4. Make the root node a standalone doubly linked list node by setting its left and right pointers to null.
  5. If a left list exists, find its rightmost (tail) node and link it with the root: set tail.right = root and root.left = tail.
  6. If a right list exists, link the root with the head of the right list: set root.right = rightList and rightList.left = root.
  7. Return the head of the combined doubly linked list (the head of the left list if it exists, otherwise the root).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>
#include <stdlib.h>

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

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

TreeNode* treeToDLL(TreeNode* root) {
    if (root == NULL) return NULL;
    TreeNode* leftList = treeToDLL(root->left);
    TreeNode* rightList = treeToDLL(root->right);
    root->left = root->right = NULL;
    TreeNode* head;
    if (leftList) {
        head = leftList;
        TreeNode* tail = leftList;
        while (tail->right) {
            tail = tail->right;
        }
        tail->right = root;
        root->left = tail;
    } else {
        head = root;
    }
    if (rightList) {
        root->right = rightList;
        rightList->left = root;
    }
    return head;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->right->left = createNode(5);
    root->right->right = createNode(6);

    TreeNode* dllHead = treeToDLL(root);
    TreeNode* curr = dllHead;
    while (curr) {
        printf("%d", curr->val);
        if (curr->right) printf(" <-> ");
        curr = curr->right;
    }
    printf("\n");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...