The O(n) Club: Merge Two Binary Trees: Where Recursion Meets the Forest for the Trees

The O(n) Club: Merge Two Binary Trees—Where Recursion Meets the Forest for the Trees

⚡ TL;DR

Boss says, “Take two binary trees, smoosh them together, and if both have a node in the same spot, add ’em up. If not? Just keep whichever node actually exists.” Think of it as making a smoothie out of leftover fruit—the result is deliciously recursive. Here’s the brute force Java:

// Recursive Java merge
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null) return t2;
    if (t2 == null) return t1;
    TreeNode merged = new TreeNode(t1.val + t2.val);
    merged.left = mergeTrees(t1.left, t2.left);
    merged.right = mergeTrees(t1.right, t2.right);
    return merged;
}

🧠 How Devs Usually Mess This Up

95% of rookie mistakes: treat one tree as “dominant” (sorry, no monarchy here), ignore that a node could be missing from either tree, or forget to lovingly check for null and then boom—NullPointerException ruining your day harder than an off-by-one error at 5PM. If you mutate the inputs when you were supposed to return a shiny new tree, you’ll make everybody cry (especially your interviewer).

🔍 What’s Actually Going On

Think of merging like reconciling filesystem trees: where folders line up, you combine their contents. Where one side is missing, you just keep whatever you have. Every corresponding node is a merge party; if one invitation is lost, the other gets full access to the drinks table. Recursion works wonders because at each merge step, you can let the JVM stack do the babysitting down both left and right branches. Smooth as butter—or at least as smooth as a directory diff can be.

🛠️ PseudoCode

• If t1 is null, return t2. (All the way up the stack, please!)
• If t2 is null, return t1. (Hey, that’s fair.)
• Otherwise:
  • Create new TreeNode with value t1.val + t2.val
  • Set left child to mergeTrees(t1.left, t2.left)
  • Set right child to mergeTrees(t1.right, t2.right)
  • Return the new node like a proud parent

Example in Java:

// In case you forgot already
if (t1 == null) return t2;
if (t2 == null) return t1;
TreeNode merged = new TreeNode(t1.val + t2.val);
merged.left = mergeTrees(t1.left, t2.left);
merged.right = mergeTrees(t1.right, t2.right);
return merged;

💻 The Code

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
 public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If both inputs are null, congrats—you just returned null and probably saved CPU cycles.
• Trees with very weird (or lopsided) layouts? The recursion just “falls through” wherever nodes are missing.
• If in-place merge is required, be clear in the interview. This code always makes a fresh tree; go wild and hack t1 directly if they ask, but don’t assume.
• Watch your stack: If your trees are deeper than your caffeine tolerance, classic StackOverflowError awaits.
• Performance: Runs in O(N), where N is number of nodes. Space is O(H) with H = tallest tree’s height (just call stack, no extra frills).

🧠 Interviewer Brain-Tattoo

“Merging trees: where recursion is king and null checks are the royal bodyguards. Pick the survivor, add the value, and move on. No tree left behind—or at least, not unless it’s actually null.” 🌳🤖