Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        curr = root
        while curr:
            if curr.left:
                # Find the rightmost node of left subtree
                prev = curr.left
                while prev.right:
                    prev = prev.right
                # Rewire connections
                prev.right = curr.right
                curr.right = curr.left
                curr.left = None
            curr = curr.right
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* curr = root;
        while (curr) {
            if (curr->left) {
                // Find the rightmost node of left subtree
                TreeNode* prev = curr->left;
                while (prev->right) {
                    prev = prev->right;
                }
                // Rewire connections
                prev->right = curr->right;
                curr->right = curr->left;
                curr->left = nullptr;
            }
            curr = curr->right;
        }
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // Find the rightmost node of left subtree
                TreeNode prev = curr.left;
                while (prev.right != null) {
                    prev = prev.right;
                }
                // Rewire connections
                prev.right = curr.right;
                curr.right = curr.left;
                curr.left = null;
            }
            curr = curr.right;
        }
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    let curr = root;
    while (curr) {
        if (curr.left) {
            // Find rightmost node in left subtree
            let prev = curr.left;
            while (prev.right) {
                prev = prev.right;
            }
            // Rewire connections
            prev.right = curr.right;
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
};
      

Problem Description

Given the root of a binary tree, you are to flatten the tree into a "linked list" in-place. The linked list should use the same TreeNode structure, but every node's right pointer should point to the next node in a pre-order traversal, and every node's left pointer should be set to null.

• Modify the tree in-place (do not create new nodes).
• Each node's right child points to the next node of the pre-order traversal.
• Each node's left child is set to null.
• There is only one valid way to flatten the tree for any given input.

Thought Process

The first step is to understand how a binary tree can be represented as a linked list using only the right pointers. Since the required order is pre-order traversal (root, left, right), we need to arrange the nodes so that each node's right pointer points to the next node in this traversal order.

A brute-force approach might involve performing a pre-order traversal, storing the nodes in a list, and then rewiring their left and right pointers accordingly. However, this would use extra space, which goes against the "in-place" requirement. To optimize, we need a way to rearrange the pointers as we traverse the tree, without using extra storage.

The key insight is that for each node with a left child, we can find the rightmost node of its left subtree and attach the current node's right subtree there. Then, we move the left subtree to the right and set the left pointer to null. This process can be repeated as we traverse the tree.

Solution Approach

• Iterative In-Place Traversal: Start from the root and move along the right pointers.
  • If the current node has a left child:
    • Find the rightmost node of the left subtree (this is where the right subtree should be attached).
    • Connect the right subtree to this rightmost node's right pointer.
    • Move the left subtree to the right pointer of the current node.
    • Set the left pointer of the current node to null.
  • Move to the next node by following the right pointer (since the left pointer is now null).
• Why this works: This approach ensures that we always maintain the pre-order sequence. By attaching the right subtree to the rightmost node of the left subtree, we guarantee that after the left subtree is traversed, we immediately continue to the former right subtree.
• No extra space: All operations are performed in-place, modifying the existing tree structure without using additional data structures.

Example Walkthrough

Let's work through an example with this tree:

      1
     / \
    2   5
   / \   \
  3   4   6
  

1. Start at node 1. It has a left child (2).
   • Find the rightmost node in the left subtree: 4.
   • Attach 1's right subtree (5) to 4's right.
   • Move left subtree (2) to 1's right.
   • Set 1's left to null.
2. Tree now looks like:

         1
          \
           2
          / \
         3   4
              \
               5
                \
                 6
         

3. Move to node 2. It has a left child (3).
   • Rightmost node of left subtree is 3.
   • Attach 2's right subtree (4) to 3's right.
   • Move left subtree (3) to 2's right.
   • Set 2's left to null.
4. Tree now looks like:

         1
          \
           2
            \
             3
              \
               4
                \
                 5
                  \
                   6
         

5. Continue moving right (nodes 3, 4, 5, 6), but none have left children, so nothing changes.
6. The tree is now flattened into a linked list following pre-order traversal: 1 → 2 → 3 → 4 → 5 → 6.

Time and Space Complexity

• Brute-force approach:
  • Time: O(N) for traversal + O(N) for rewiring = O(N)
  • Space: O(N) for storing nodes in a list
• Optimized in-place approach (as above):
  • Time: O(N), since each node is visited and rewired at most once.
  • Space: O(1), as all modifications are done in-place and no extra data structures are used.

The optimized approach is both time and space efficient, making it suitable for large trees.

Summary

To flatten a binary tree to a linked list in pre-order traversal, we iteratively rearrange pointers in-place. By always attaching the original right subtree to the rightmost node of the left subtree and moving the left subtree to the right, we ensure the correct order without using extra space. This approach is efficient, elegant, and leverages the structure of the binary tree for optimal pointer manipulation.