Convert Binary tree into Doubly Linked List

Problem Statement

Given a binary tree, convert it to a doubly linked list (DLL) in-place. The left pointer of the tree node should act as the previous pointer of DLL, and the right pointer should act as the next pointer. The DLL should follow the inorder traversal of the tree.

Example:

Approach 1: Using Inorder Traversal with Array

Intuition

Perform inorder traversal, store all nodes in an array, then link them together.

Algorithm

1. Perform inorder traversal and collect all nodes
2. Link each node to its neighbors in the array
3. First node's prev = null, last node's next = null

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private void inorder(TreeNode root, List<TreeNode> nodes) {
        if (root == null) return;
        
        inorder(root.left, nodes);
        nodes.add(root);
        inorder(root.right, nodes);
    }
    
    public TreeNode binaryTreeToDLL(TreeNode root) {
        if (root == null) return null;
        
        List<TreeNode> nodes = new ArrayList<>();
        inorder(root, nodes);
        
        // Link nodes
        for (int i = 0; i < nodes.size(); i++) {
            nodes.get(i).left = (i > 0) ? nodes.get(i - 1) : null;
            nodes.get(i).right = (i < nodes.size() - 1) ? nodes.get(i + 1) : null;
        }
        
        return nodes.get(0);  // Head of DLL
    }
}

Complexity Analysis

• Time Complexity: O(n) - Inorder traversal + linking
• Space Complexity: O(n) - Array stores all nodes

Approach 2: Optimal (In-place Conversion)

Intuition

During inorder traversal, maintain a pointer to the previously visited node. Link the previous node's right to current, and current's left to previous.

Algorithm

1. Track the previous node during inorder traversal
2. Link prev.right = current and current.left = prev
3. Update prev to current after processing
4. Return the leftmost node as head

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode prev;
    private TreeNode head;
    
    private void inorder(TreeNode root) {
        if (root == null) return;
        
        // Process left subtree
        inorder(root.left);
        
        // Process current node
        if (prev == null) {
            // First node - this is the head
            head = root;
        } else {
            // Link previous node with current
            prev.right = root;
            root.left = prev;
        }
        prev = root;
        
        // Process right subtree
        inorder(root.right);
    }
    
    public TreeNode binaryTreeToDLL(TreeNode root) {
        if (root == null) return null;
        
        prev = null;
        head = null;
        
        inorder(root);
        
        return head;
    }
    
    public TreeNode binaryTreeToCircularDLL(TreeNode root) {
        if (root == null) return null;
        
        prev = null;
        head = null;
        
        inorder(root);
        
        // Make it circular
        head.left = prev;
        prev.right = head;
        
        return head;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single inorder traversal
• Space Complexity: O(h) - Recursion stack, where h is height

Approach 3: Morris Traversal (True O(1) Space)

Intuition

Use Morris traversal to achieve O(1) space (ignoring output). This modifies the tree during traversal but restores it while building the DLL.

Algorithm

1. Use Morris inorder traversal
2. Track prev and head as before
3. Link nodes during the traversal

Complexity Analysis

• Time Complexity: O(n) - Each edge traversed at most twice
• Space Complexity: O(1) - No extra space (in-place)

Utility: Print DLL

Key Takeaways

1. Inorder traversal naturally gives sorted DLL for BST
2. Key insight: Use prev pointer to link nodes during traversal
3. Three approaches: Array (easy), recursive (optimal), Morris (space-optimal)
4. Circular DLL: Just connect head and tail at the end
5. left pointer = prev, right pointer = next in the DLL
6. This is a popular interview question combining tree and linked list concepts
7. Same technique can be used to flatten BST to sorted linked list