How to Convert Binary Tree to Doubly Linked List

Introduction

Converting a binary tree to a doubly linked list (DLL) is a common problem in tree manipulation. The objective is to perform an in-place transformation where the left and right pointers of tree nodes are used as previous and next pointers in the resulting DLL. In this article, we demonstrate how to perform this conversion using an in-order traversal approach in Java.

Problem Statement

Given a binary tree, transform it into a doubly linked list in such a way that the order of nodes in the list reflects the in-order traversal of the tree. Each node’s left pointer functions as the previous link, while the right pointer serves as the next link in the doubly linked list.

Approach

The most intuitive method to achieve this is through in-order traversal, which visits nodes in ascending order for a binary search tree. We keep track of the previously visited node and adjust pointers as we go. The head of the doubly linked list is the leftmost node in the tree.

We use a helper function that recursively traverses the tree in-order, and modifies the left and right pointers of the nodes to stitch them together into a DLL.

Java Implementation

class BinaryTreeToDLL {
	
    static class BinTreeNode {
        int data;
        BinTreeNode left, right;

        BinTreeNode(int data) {
            this.data = data;
            this.left = this.right = null;
        }
    }

    static class Converter {
        BinTreeNode prev = null;
        BinTreeNode head = null;

        public void convertToDLL(BinTreeNode root) {
            if (root == null) return;

            convertToDLL(root.left);

            if (prev == null) {
                head = root;
            } else {
                root.left = prev;
                prev.right = root;
            }
            prev = root;

            convertToDLL(root.right);
        }

        public BinTreeNode getHead() {
            return head;
        }
    }

    public static void printDLL(BinTreeNode head) {
        BinTreeNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.right;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BinTreeNode root = new BinTreeNode(10);
        root.left = new BinTreeNode(6);
        root.right = new BinTreeNode(14);
        root.left.left = new BinTreeNode(4);
        root.left.right = new BinTreeNode(8);
        root.right.left = new BinTreeNode(12);
        root.right.right = new BinTreeNode(16);

        Converter converter = new Converter();
        converter.convertToDLL(root);
        BinTreeNode dllHead = converter.getHead();

        System.out.println("Doubly Linked List:");
        printDLL(dllHead);
    }
}

Example Explanation

Consider the binary tree:

markdownCopiaModifica        10
       /  \
      6    14
     / \   / \
    4   8 12 16

In-order traversal yields: 4, 6, 8, 10, 12, 14, 16
The resulting doubly linked list will have nodes linked in this exact order using the left and right pointers of the original tree nodes.

Conclusion

Converting a binary tree to a doubly linked list is an elegant problem that leverages recursive traversal and pointer manipulation. The in-order approach ensures the doubly linked list maintains a sorted order, especially useful for binary search trees. This transformation is done in-place without using extra data structures, making it efficient in terms of space. Utilizing a queue simplifies the process and enhances efficiency. Gaining familiarity with this approach lays a solid foundation for tackling more advanced tree algorithms in the future.

You can find the example code on Github.