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

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