Flatten Binary tree to double linked list in-place

Problem

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) (In-Place).

Detailed

Given a binary tree, convert it into a doubly linked list (DLL) in-place. The DLL should represent the in-order traversal of the binary tree, where the left child becomes the previous link, and the right child becomes the next link of the DLL.

Examples

Example 1

For example for the input:

Input:
     10
    /  \
   12   15
  / \
 25  30
 
Output: 
25 <-> 12 <-> 30 <-> 10 <-> 15

Explanation: The in-order traversal of the binary tree gives [25, 12, 30, 10, 15]. These nodes must be linked as a doubly linked list.

Output:

1 <-> 4 <-> 5 <-> 6 <-> 8 <-> 10 <-> 11

Solution

As we discussed earlier we can reuse left and right pointers to connect link list nodes so, we can create DLL by doing inorder traversal and connecting nodes by their left and right nodes along the traversal path.

First question you should be asking is which node should be the head of doubly linked list? If left most node in binary tree is to be head, you need to traverse tree in inorder. However if root node has to be head node, then you should do preorder traversal.

To convert binary tree to linked list,   at each node, previous pointer will point to the inorder predecessor of the node where as next pointer points to inorder successor of node.

Method 1 - Recursion

The in-order traversal of a binary tree is a natural choice for converting it into a doubly linked list because the left-to-right order of nodes perfectly aligns with the sequential arrangement in a DLL.

The goal is to:

1. Traverse the binary tree in in-order fashion.
2. Link the nodes being visited such that the left pointer represents the previous node, and the right pointer represents the next node in the resultant doubly linked list.

Approach

1. Perform an in-order traversal of the binary tree recursively.
2. Maintain a reference (prev) to the previously visited node to connect it with the current node.
3. Update the left and right pointers for DLL linkage.
4. Ensure the conversion happens in-place by adjusting the tree’s pointers directly.

Code

Java

class Solution {
    // Pointer to track previous node as we traverse
    private TreeNode prev = null;

    // Method to convert Binary Tree to Doubly Linked List
    public TreeNode BTtoDLL(TreeNode root) {
        if (root == null) return null;

        // Dummy node to help establish the head of DLL
        TreeNode dummy = new TreeNode(-1);
        prev = dummy;

        // Helper recursive function
        inorderTraversal(root);

        // The right of the dummy node will be the head of our DLL
        TreeNode head = dummy.right;
        if (head != null) head.left = null; // Head's left pointer must be null
        return head;
    }

    // Recursive in-order traversal
    private void inorderTraversal(TreeNode curr) {
        if (curr == null) return;

        // Left subtree
        inorderTraversal(curr.left);

        // Current node manipulation
        prev.right = curr; // Connect previous node's right to current node
        curr.left = prev;  // Connect current node's left to previous node
        prev = curr;       // Move prev pointer to current node

        // Right subtree
        inorderTraversal(curr.right);
    }

    // Utility method to print DLL
    public void printDLL(TreeNode head) {
        TreeNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " <-> ");
            temp = temp.right;
        }
        System.out.println("null");
    }
}

Python

class Solution:

    def __init__(self):
        self.prev = None  # Pointer to track previous node

    def BTtoDLL(self, root):
        if not root:
            return None

        # Dummy node to help establish the head of DLL
        dummy = self.TreeNode(-1)
        self.prev = dummy
        
        # Helper recursive function
        self.inorderTraversal(root)
        
        # The right of the dummy node will be the head of our DLL
        head = dummy.right
        if head:
            head.left = None  # Head's left pointer must be null
        return head
        
    def inorderTraversal(self, curr):
        if not curr:
            return

        # Left subtree
        self.inorderTraversal(curr.left)
        
        # Current node manipulation
        self.prev.right = curr  # Connect previous node's right to current node
        curr.left = self.prev   # Connect current node's left to previous node
        self.prev = curr        # Move prev pointer to current node
        
        # Right subtree
        self.inorderTraversal(curr.right)
        
    # Utility method to print DLL
    def printDLL(self, head):
        temp = head
        while temp:
            print(temp.val, end=" <-> ")
            temp = temp.right
        print("null")

Complexity

• ⏰ Time complexity: O(n) because we traverse each node of the binary tree exactly once.
• 🧺 Space complexity: O(h) where h is the height of the binary tree due to the recursive call stack.

Method 2 - Update inorder predecessor and successor

The solution involves two straightforward steps:

1. Fix Left Pointers: Perform an in-order traversal on the binary tree to update the left pointers of each node. During the traversal, maintain a reference to the previously visited node and set the left pointer to point to it. This establishes the preceding relationships in the Doubly Linked List (DLL).
2. Fix Right Pointers: Starting from the rightmost node (the last node in the DLL), traverse the left pointers linearly from end to start. As you move through the nodes, update the right pointers to point to the previously visited node, completing the DLL connections.

Code

Java

class Solution {
    // Fix left pointers using in-order traversal
    private TreeNode fixPrevPtr(TreeNode root) {
        TreeNode prev = null;
        if (root != null) {
            // Recur for the left subtree
            prev = fixPrevPtr(root.left);
            
            // Set left pointer to the previous node
            root.left = prev;

            // Update previous node to current node
            prev = root;

            // Recur for the right subtree
            prev = fixPrevPtr(root.right);
        }
        return prev;
    }

    // Fix right pointers using the already fixed left pointers
    private TreeNode fixNextPtr(TreeNode root) {
        // Start from the rightmost node
        while (root.right != null) {
            root = root.right;
        }

        // Traverse from rightmost to leftmost
        TreeNode prev = null;
        while (root != null) {
            root.right = prev; // Fix right pointer
            prev = root;       // Move prev pointer
            root = root.left;  // Move to the previous node in DLL
        }

        return prev; // Return the head of the DLL
    }

    // Convert a Binary Tree to Doubly Linked List
    public TreeNode BTtoDLL(TreeNode root) {
        if (root == null) return null;

        // Step 1: Fix left pointers
        fixPrevPtr(root);

        // Step 2: Fix right pointers
        return fixNextPtr(root); // The returned node is now the head of DLL
    }

    // Utility to print the DLL
    public void printDLL(TreeNode head) {
        TreeNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " <-> ");
            temp = temp.right;
        }
        System.out.println("null");
    }
}

Python

class Solution:
    # Fix left pointers using in-order traversal
    def fixPrevPtr(self, root):
        prev = None
        stack = []  # Stack for in-order traversal
        current = root

        while stack or current:
            # Traverse the left subtree
            while current:
                stack.append(current)
                current = current.left

            # Visit the node
            current = stack.pop()
            current.left = prev  # Fix left pointer
            prev = current       # Update prev node

            # Traverse the right subtree
            current = current.right

        return prev

    # Fix right pointers using the already fixed left pointers
    def fixNextPtr(self, root):
        # Move to the rightmost node
        while root.right:
            root = root.right

        prev = None
        # Traverse from rightmost to leftmost
        while root:
            root.right = prev  # Fix right pointer
            prev = root         # Update prev pointer
            root = root.left    # Move to the previous node in DLL

        return prev  # Return the head of the DLL

    # Convert a Binary Tree to Doubly Linked List
    def BTtoDLL(self, root):
        if not root:
            return None
        
        # Step 1: Fix left pointers
        self.fixPrevPtr(root)

        # Step 2: Fix right pointers
        return self.fixNextPtr(root)  # The returned node is the head of DLL

    # Utility function to print the DLL
    def printDLL(self, head):
        temp = head
        while temp:
            print(temp.data, end=" <-> ")
            temp = temp.right
        print("null")

Complexity

• ⏰ Time complexity: O(n).
  • This involves an in-order traversal of the binary tree which visits each node exactly once, which takes O(n).
  • After the left pointers are fixed, traversing the nodes linearly via left pointers (from the last node to the first) also involves visiting all the nodes once. This takes O(n).
• 🧺 Space complexity: O(h). The space complexity of recursion (or iterative traversal) comes into play due to the call stack.