The O(n) Club: Flatten Binary Tree to Linked List, Minus the Screaming

The O(n) Club: Flatten Binary Tree to Linked List, Minus the Screaming

⚡ TL;DR

Take your binary tree and wrestle it into a right-child-only parade—every node’s left pointer gets ghosted, and we follow a pre-order march. Here’s the Java in-a-nutshell version:

// Conceptual Java quickie
void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    TreeNode temp = root.right;
    root.right = root.left;
    root.left = null;
    TreeNode current = root;
    while (current.right != null) {
        current = current.right;
    }
    current.right = temp;
}

🧠 How Devs Usually Mess This Up

Instead of following pre-order like a developer with a calendar invite, people:

• Go with in-order or post-order, imagining traversal order is a social construct. Spoiler: it’s not for this problem.
• Use fancy new lists or arrays, when interviewers want you to do some classic pointer burpees—literally in-place, no life preservers.
• Forget to set left = null, so nodes keep holding onto their exes out of spite.
• Ignore edge cases—like single-sided trees or empties—because “we’re just testing, right?” (Wrong.)

🔍 What’s Actually Going On

Imagine your binary tree as your laptop’s folders. Now, someone wants you to flatten all those folders into a single PowerPoint slide, where every right arrow shows you the next thing you’d see in pre-order. Left folders? They’re about as useful now as a floppy disk. Flip every left pointer to null, shove the left subtree over to the right, and jam the old right bits onto the end. Like a pizza oven: what goes left comes out right.

You’re not allowed to allocate a new backing array or hold a reference list—everything has to be surgically rearranged using good old pointers. If you’re lost, think: “What would a sleep-deprived file system do?”

🛠️ PseudoCode

• Check for empty root: Hit return, chill.

  if (root == null) return;

• Recursively flatten the left subtree.

  flatten(root.left);

• Recursively flatten the right subtree.

  flatten(root.right);

• Store the original right subtree.

  TreeNode temp = root.right;

• Bounce the left subtree rightward, erase the left.

  root.right = root.left;
  root.left = null;

• Slide down the new right chain to its end.

  TreeNode current = root;
  while (current.right != null) {
      current = current.right;
  }

• Glue the saved right subtree back on.

  current.right = temp;

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 public void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    TreeNode temp = root.right;
    root.right = root.left;
    root.left = null;
    TreeNode current = root;
    while (current.right != null) {
        current = current.right;
    }
    current.right = temp;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Get the order right: Pre-order is law. Mess it up and watch your interviewer’s eyebrow twitch.
• Memory leaks: If you forget to null the left pointers, half your tree keeps lurking in the shadows.
• Stack strain: For truly massive trees, recursion adds up. You get O(n) space from the call stack. Not a LinkedList, but not free either.
• All the corners: Don’t skip empty trees or trees with only a single child when testing, unless you love re-interviewing.
• Optimized O(1) space solution: Yeah, you could use Morris Traversal—but only if you like living on the edge (and explaining really fast in interviews).

🧠 Interviewer Brain-Tattoo

“Pre-order or pre-regret—flatten in-place, null your exes, and always test the corner cases. Because trees have more secrets than your codebase.”