ProgramGuru

Convert a Binary Tree into a Doubly Linked List

Problem and examples

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.
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

How it works

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.

  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).

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

TreeNode* treeToDLL(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* leftList = treeToDLL(root->left);
    TreeNode* rightList = treeToDLL(root->right);
    root->left = root->right = nullptr;
    TreeNode* head = leftList ? leftList : root;
    if (leftList) {
        TreeNode* tail = leftList;
        while (tail->right)
            tail = tail->right;
        tail->right = root;
        root->left = tail;
    }
    if (rightList) {
        root->right = rightList;
        rightList->left = root;
    }
    return head;
}

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

    TreeNode* dllHead = treeToDLL(root);
    TreeNode* curr = dllHead;
    while (curr) {
        cout << curr->val;
        if (curr->right) cout << " <-> ";
        curr = curr->right;
    }
    cout << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def treeToDLL(root):
    if not root:
        return None
    leftList = treeToDLL(root.left)
    rightList = treeToDLL(root.right)
    root.left = root.right = None
    if leftList:
        tail = leftList
        while tail.right:
            tail = tail.right
        tail.right = root
        root.left = tail
    else:
        leftList = root
    if rightList:
        root.right = rightList
        rightList.left = root
    return leftList

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6)))
    dllHead = treeToDLL(root)
    curr = dllHead
    while curr:
        print(curr.val, end=' <-> ' if curr.right else '\n')
        curr = curr.right

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class BinaryTreeToDLL {
    public TreeNode treeToDLL(TreeNode root) {
        if (root == null) return null;
        TreeNode leftList = treeToDLL(root.left);
        TreeNode rightList = treeToDLL(root.right);
        root.left = root.right = null;
        if (leftList != null) {
            TreeNode tail = leftList;
            while (tail.right != null) tail = tail.right;
            tail.right = root;
            root.left = tail;
        } else {
            leftList = root;
        }
        if (rightList != null) {
            root.right = rightList;
            rightList.left = root;
        }
        return leftList;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        BinaryTreeToDLL converter = new BinaryTreeToDLL();
        TreeNode dllHead = converter.treeToDLL(root);
        TreeNode curr = dllHead;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.right != null) System.out.print(" <-> ");
            curr = curr.right;
        }
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function treeToDLL(root) {
    if (!root) return null;
    const leftList = treeToDLL(root.left);
    const rightList = treeToDLL(root.right);
    root.left = root.right = null;
    let head = leftList || root;
    if (leftList) {
        let tail = leftList;
        while (tail.right) tail = tail.right;
        tail.right = root;
        root.left = tail;
    }
    if (rightList) {
        root.right = rightList;
        rightList.left = root;
    }
    return head;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3, new TreeNode(5), new TreeNode(6)));
let dllHead = treeToDLL(root);
let curr = dllHead;
let output = [];
while (curr) {
    output.push(curr.val);
    curr = curr.right;
}
console.log(output.join(' <-> '));

Go implementation

package main

import "fmt"

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

func treeToDLL(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    leftList := treeToDLL(root.left)
    rightList := treeToDLL(root.right)
    root.left, root.right = nil, nil
    head := root
    if leftList != nil {
        head = leftList
        tail := leftList
        for tail.right != nil {
            tail = tail.right
        }
        tail.right = root
        root.left = tail
    }
    if rightList != nil {
        root.right = rightList
        rightList.left = root
    }
    return head
}

func createTree() *TreeNode {
    return &TreeNode{1,
        &TreeNode{2, &TreeNode{4, nil, nil}, nil},
        &TreeNode{3, &TreeNode{5, nil, nil}, &TreeNode{6, nil, nil}},
    }
}

func main() {
    root := createTree()
    head := treeToDLL(root)
    for node := head; node != nil; node = node.right {
        fmt.Print(node.val)
        if node.right != nil {
            fmt.Print(" <-> ")
        }
    }
    fmt.Println()
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn main() {
    println!("This Rust version would require extensive unsafe code or refcell logic for pointers, so skipping implementation for brevity.");
}

Kotlin implementation

class TreeNode(var val_: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun treeToDLL(root: TreeNode?): TreeNode? {
    if (root == null) return null
    val leftList = treeToDLL(root.left)
    val rightList = treeToDLL(root.right)
    root.left = null
    root.right = null
    var head = leftList ?: root
    if (leftList != null) {
        var tail = leftList
        while (tail?.right != null) tail = tail.right
        tail?.right = root
        root.left = tail
    }
    if (rightList != null) {
        root.right = rightList
        rightList.left = root
    }
    return head
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2).apply { left = TreeNode(4) }
    root.right = TreeNode(3).apply {
        left = TreeNode(5)
        right = TreeNode(6)
    }
    var curr = treeToDLL(root)
    while (curr != null) {
        print(curr.val_)
        if (curr.right != null) print(" <-> ")
        curr = curr.right
    }
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function treeToDLL(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const leftList = treeToDLL(root.left);
    const rightList = treeToDLL(root.right);
    root.left = root.right = null;
    let head = leftList || root;
    if (leftList) {
        let tail = leftList;
        while (tail.right) tail = tail.right;
        tail.right = root;
        root.left = tail;
    }
    if (rightList) {
        root.right = rightList;
        rightList.left = root;
    }
    return head;
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4)),
    new TreeNode(3, new TreeNode(5), new TreeNode(6))
);
let curr: TreeNode | null = treeToDLL(root);
const result: number[] = [];
while (curr) {
    result.push(curr.val);
    curr = curr.right;
}
console.log(result.join(' <-> '));