Advanced Tree Operations: Transformation and Serialization

Design Principle: When modifying a tree's physical structure, it is often best to process child subtrees completely before restructuring the parent (Post-order processing).

Flatten Binary Tree to Linked List (LeetCode 114)

Flatten a binary tree into a "right-only" linked list in place, following its pre-order traversal sequence.

Approach 1: Iterative (Morris-Inspired)

public void flatten(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left != null) {
            // Locate the rightmost node in the left subtree
            TreeNode rightmost = curr.left;
            while (rightmost.right != null) {
                rightmost = rightmost.right;
            }
            // Splice current's right subtree onto the rightmost of left subtree
            rightmost.right = curr.right;
            // Shift current's left subtree to its right side
            curr.right = curr.left;
            curr.left = null;
        }
        // Move down the chain
        curr = curr.right;
    }
}

Efficiency: O(n) Time, O(1) Space.

Approach 2: Recursive Post-order

private TreeNode previousNode = null;

public void flatten(TreeNode root) {
    if (root == null) return;
    // Walk backward relative to pre-order: Right -> Left -> Root
    flatten(root.right);
    flatten(root.left);
    
    // Stitch current node into the chain
    root.right = previousNode;
    root.left = null;
    previousNode = root;
}

Populating Next Right Pointers in Each Node (LeetCode 116/117)

116. Perfect Binary Tree (Constant Space)

public Node connect(Node root) {
    if (root == null) return null;
    Node leftmost = root;
    
    while (leftmost.left != null) { // Move through levels
        Node curr = leftmost;
        while (curr != null) {
            // Case 1: Connect immediate children of the same parent
            curr.left.next = curr.right;
            // Case 2: Connect right child to the left child of neighbor
            if (curr.next != null) {
                curr.right.next = curr.next.left;
            }
            curr = curr.next;
        }
        leftmost = leftmost.left;
    }
    return root;
}

117. Any Binary Tree (Handles Null Gaps)

Use a dummy head to build the linked list of the next level while traversing the current level:

public Node connect(Node root) {
    Node curr = root;
    while (curr != null) {
        Node dummy = new Node(0); // Dummy for the next level
        Node tail = dummy;
        while (curr != null) {
            if (curr.left != null) {
                tail.next = curr.left;
                tail = tail.next;
            }
            if (curr.right != null) {
                tail.next = curr.right;
                tail = tail.next;
            }
            curr = curr.next;
        }
        curr = dummy.next; // Pivot to the start of the next level
    }
    return root;
}

Invert Binary Tree (LeetCode 226)

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode temp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(temp);
    return root;
}

Serialize and Deserialize Binary Tree (LeetCode 297)

Using pre-order traversal with a special character (#) for null markers.

// Serialization: Root,Left,Right...
public String serialize(TreeNode root) {
    if (root == null) return "#";
    return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}

// Deserialization
public TreeNode deserialize(String data) {
    Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
    return rebuild(nodes);
}

private TreeNode rebuild(Queue<String> nodes) {
    String value = nodes.poll();
    if ("#".equals(value)) return null;
    
    TreeNode node = new TreeNode(Integer.parseInt(value));
    node.left = rebuild(nodes);
    node.right = rebuild(nodes);
    return node;
}

Summary Table