Convert BST to Sorted Doubly Linkedlist

426.Convert Binary Search Tree to Sorted Doubly Linked List

Tree

Linked List

Depth First Search

Problem Statement:

Convert a BST to a sorted circular doubly-linked list in-place. The left and right pointers should point to the previous and next nodes in the linked list respectively.

Java Solution (Iterative):

public Node treeToDoublyListIterative(Node root) {
    if (root == null) return null;
    Node dummy = new Node(), last = dummy, curr = root;
    Stack s = new Stack<>();
    // REMEMBER DON"T INIT STACK WITH CURR IN ITERATIVE DFS!

    while (curr != null || !s.isEmpty()) {
        // Go left as far as possible
        while (curr != null) {
            s.push(curr);
            curr = curr.left;
        }

        curr = s.pop();

        // Link nodes in doubly linked list
        last.right = curr;
        curr.left = last;
        last = curr;

        curr = curr.right;
    }

    // Make circular
    Node first = dummy.right;
    last.right = first;
    first.left = last;

    return first;
}

Java Solution (Morris Traversal):

// Morris Traversal
public Node treeToDoublyList(Node root) {
    if (root == null) return null;
    Node dummy = new Node(), last = dummy, curr = root;

    while (curr != null) {
        if (curr.left != null) {
            // Find predecessor
            Node predecessor = curr.left;
            while (predecessor.right != curr && predecessor.right != null)
                predecessor = predecessor.right;

            if (predecessor.right == curr) {
                // Remove thread and process node
                predecessor.right = null;
                
                last.right = curr;
                curr.left = last;
                last = curr;
                
                curr = curr.right;
            } else {
                // Create thread and go left
                predecessor.right = curr;
                curr = curr.left;
            }
        } else {
            // Process node and go right
            last.right = curr;
            curr.left = last;
            last = curr;
            
            curr = curr.right;
        }
    }

    // Make circular
    Node first = dummy.right;
    last.right = first;
    first.left = last;

    return first;
}

Key Differences:

1. Iterative: Uses extra space O(H) for stack
2. Morris: O(1) space by using temporary thread links
3. Both maintain inorder traversal order
4. Morris avoids stack but modifies tree temporarily

Complexity:

Iterative: Time O(N), Space O(H)
Morris: Time O(N), Space O(1)