Convert a Binary Tree into a Doubly Linked List - Algorithm & Code Examples

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❯

Case 1: Normal Binary Tree

In a typical binary tree with both left and right children, such as one with nodes [10, 5, 15], we perform an in-order traversal: left subtree (5), root (10), right subtree (15). Each visited node is linked to the previous one using the left and right pointers to create the doubly linked list. The resulting list becomes 5 <-> 10 <-> 15.

Case 2: Single Node Tree

If the tree contains only one node (e.g., [10]), that node itself becomes the doubly linked list. Since there are no left or right children, both pointers remain null. So, the list is just 10.

Case 3: Empty Tree

If the input tree is empty (null or empty array), there’s nothing to convert. Therefore, the output should also be null.

Case 4: Right Skewed Tree

In this structure, each node only has a right child, such as [10, null, 20, null, 30]. The in-order traversal here simply visits each node in sequence from top to bottom: 10 → 20 → 30. The doubly linked list will also reflect this same order: 10 <-> 20 <-> 30.

Case 5: Left Skewed Tree

For a tree where each node only has a left child, like [30, 20, null, 10, null], the traversal goes from bottom to top (leftmost to root): 10 → 20 → 30. The doubly linked list follows this ascending order: 10 <-> 20 <-> 30.

Algorithm Steps❯

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

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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
    # Recursively convert left and right subtrees
    leftList = treeToDLL(root.left)
    rightList = treeToDLL(root.right)
    # Make root a standalone DLL node
    root.left = root.right = None
    # Attach left list to root
    if leftList:
        tail = leftList
        while tail.right:
            tail = tail.right
        tail.right = root
        root.left = tail
    else:
        leftList = root
    # Attach right list to root
    if rightList:
        root.right = rightList
        rightList.left = root
    return leftList

# Example usage:
if __name__ == '__main__':
    # Construct a sample binary tree
    #         1
    #        / \
    #       2   3
    #      /   / \
    #     4   5   6
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6)))
    dllHead = treeToDLL(root)
    # Print the doubly linked list from left to right
    curr = dllHead
    while curr:
        print(curr.val, end=' <-> ' if curr.right else '\n')
        curr = curr.right

⬅ Previous TopicConstruct a Binary Tree from a String with Bracket Representation

Next Topic ⮕Convert a Binary Tree into a Sum Tree