Flatten Binary Tree to Linked List

• If the root is null, return immediately.
• Create an empty List<TreeNode> to store the nodes.
• Perform a pre-order traversal on the tree. In the traversal, add each visited node to the list.
• Iterate through the list from the first element up to the second-to-last element.
• For each node at index i, set its left pointer to null and its right pointer to the node at index i+1.
• Set the left and right pointers of the last node in the list to null.

The core idea is to separate the traversal from the restructuring. First, we perform a standard pre-order traversal (Root, Left, Right) on the tree. We can use a recursive helper function for this. During the traversal, every node we encounter is added to a dynamic array or list. Once the traversal is complete, this list holds all the tree nodes in the exact sequence required for the flattened list. The second step is to iterate through this list of nodes from the beginning. For each node at index i, we set its left child to null and its right child to the node at index i+1. This process effectively links all the nodes together. The last node in the list will have its right child set to null, terminating the flattened list.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public void flatten(TreeNode root) {18        if (root == null) {19            return;20        }21        List<TreeNode> nodes = new ArrayList<>();22        preorderTraversal(root, nodes);23        24        for (int i = 0; i < nodes.size() - 1; i++) {25            TreeNode curr = nodes.get(i);26            TreeNode next = nodes.get(i + 1);27            curr.left = null;28            curr.right = next;29        }30        31        // Set the last node's children to null32        TreeNode lastNode = nodes.get(nodes.size() - 1);33        lastNode.left = null;34        lastNode.right = null;35    }36    37    private void preorderTraversal(TreeNode node, List<TreeNode> nodes) {38        if (node == null) {39            return;40        }41        nodes.add(node);42        preorderTraversal(node.left, nodes);43        preorderTraversal(node.right, nodes);44    }45}

• Initialize a global or class-level TreeNode variable prev to null. This will track the previously visited node.
• Define a recursive function flatten(node).
• Base Case: If node is null, return.
• Recursively call flatten(node.right).
• Recursively call flatten(node.left).
• After the recursive calls, set node.right to prev.
• Set node.left to null.
• Update prev to be the current node.
• Call the initial flatten(root).

This approach avoids using an explicit list by performing the rewiring during the recursion itself. The key insight is to process the subtrees in a specific order: Right, Left, Root. This is a variation of a post-order traversal. We use a helper variable, prev, which keeps track of the node that was processed last (which will be the head of the already-flattened part of the tree). The recursive function works as follows:

1. It first calls itself on the right child. This flattens the entire right subtree. After this call returns, prev will point to the head of the flattened right subtree.
2. Then, it calls itself on the left child. This flattens the left subtree. The tail of this flattened left subtree will be internally linked to the prev from the previous step. After this call returns, prev will point to the head of the flattened left subtree.
3. Finally, it processes the current node. It sets the current node's right pointer to prev (linking it to the rest of the flattened list) and its left pointer to null. It then updates prev to be the current node, making it the new head of the flattened list seen so far. By starting the process from the root, the entire tree is flattened in-place.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private TreeNode prev = null;18 19    public void flatten(TreeNode root) {20        if (root == null) {21            return;22        }23        // Traverse right subtree first, then left, then process the root24        flatten(root.right);25        flatten(root.left);26        27        // Rewire the current node28        root.right = prev;29        root.left = null;30        31        // Update prev to the current node for the next step up in recursion32        prev = root;33    }34}

• Initialize a pointer curr to root.
• Start a while loop that continues as long as curr is not null.
• Inside the loop, check if curr.left is not null.
• If it is, find the rightmost node of the left subtree. Let's call it predecessor.
  • Start with predecessor = curr.left.
  • While predecessor.right is not null, update predecessor = predecessor.right.
• Perform the rewiring:
  • predecessor.right = curr.right
  • curr.right = curr.left
  • curr.left = null
• Whether curr.left was null or not, move to the next node by updating curr = curr.right.
• The loop continues until the entire tree is processed.

This iterative solution is the most space-efficient, achieving true O(1) extra space. It's based on the principles of Morris Traversal. The algorithm iterates through the tree, modifying pointers as it goes to create the flattened structure without a stack or recursion. We use a curr pointer, starting at the root. In each step of the main loop:

• If curr has no left child, it means we are already in the correct pre-order position relative to its children. We simply move to the right child (curr = curr.right) to continue.
• If curr has a left child, we need to insert the left subtree between curr and curr.right. To do this, we first find the rightmost node of the left subtree. This node is the pre-order predecessor of curr's original right child. We then perform the rewiring:
  1. Set the predecessor's right pointer to curr.right.
  2. Move the entire left subtree to curr.right.
  3. Set curr.left to null. After this rewiring, we move curr to its new right child (the former left child) and continue the process. The loop terminates when curr becomes null.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public void flatten(TreeNode root) {18        TreeNode curr = root;19        while (curr != null) {20            if (curr.left != null) {21                // Find the rightmost node in the left subtree22                TreeNode predecessor = curr.left;23                while (predecessor.right != null) {24                    predecessor = predecessor.right;25                }26                27                // Rewire the pointers28                predecessor.right = curr.right; // Connect predecessor to curr's right child29                curr.right = curr.left;         // Move left subtree to the right30                curr.left = null;               // Set left child to null31            }32            // Move to the next node in the pre-order sequence33            curr = curr.right;34        }35    }36}