Convert a Binary Tree into a Doubly Linked List

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

Convert a Binary Tree into a Doubly Linked List - Code Examples 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