Binary Tree to DLL

Time: O(n)

Space: O(h)

Intuition

In-order traversal (leftâ†’rootâ†’right) of a BST gives sorted order. Convert by linking each node's left pointer to the previous node and right pointer to the next node during in-order traversal. Track the last processed node (prev).

Algorithm

1In-order traversal. Maintain prev node.
2For each node: node.left = prev. If prev != null: prev.right = node.
3Track head (first node). Update prev = node.
4Return head.

Example Walkthrough

Input: BST: 10, left=12, right=15, 12's right=25, 15's left=36

1.In-order: 12â†’25â†’10â†’36â†’15. Link each: 12â†â†’25â†â†’10â†â†’36â†â†’15.

Output: DLL: 12â†”25â†”10â†”36â†”15

Common Pitfalls

•Link prevâ†’curr before updating prev = curr, otherwise you lose the predecessor.

Binary Tree to DLL.java

Java

// Approach: In-order traversal. Convert BST to sorted doubly linked list in-place using Morris or recursive in-order.
// Track the previous node and link current node's left to prev, prev's right to current.
// Time: O(n) Space: O(h)
import java.util.*;

class Node {
    Node left, right;
    int data;

    Node(int d) {
        data = d;
        left = right = null;
    }

}

// This function should return head to the DLL

class Solution {
    // Function to convert binary tree to doubly linked list and return it.
    Node bToDLL(Node root) {
        ArrayList<Integer> list = new ArrayList<>();

        // Perform in-order traversal and store the node values in the list
        inOrder(root, list);

        // Convert ArrayList to a doubly linked list
        return convertToDLL(list);
    }

    void inOrder(Node root, ArrayList<Integer> list) {
        if (root == null)
            return;

        inOrder(root.left, list);
        list.add(root.data);
        inOrder(root.right, list);
    }

    Node convertToDLL(ArrayList<Integer> list) {
        if (list.isEmpty())
            return null;

        Node head = new Node(list.get(0));
        Node current = head;

        for (int i = 1; i < list.size(); i++) {
            Node newNode = new Node(list.get(i));
            current.right = newNode;
            newNode.left = current;
            current = newNode;
        }

        return head;
    }
}

Was this solution helpful?