The O(n) Club: Same Tree: If You Flattened It, You Broke It

The O(n) Club: Same Tree — If You Flattened It, You Broke It

⚡ TL;DR

Stop trying to flatten, traverse, or philosophize about your trees. If you want to check whether they’re really twins, just compare each node directly, in order, recursively. Both trees empty? Sure, same. One’s got an extra branch? Not the same. Values don’t match? Nice try. Keep walking both trees node-by-node and only true friendship survives.

// Java - Recursive DFS
boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null || p.val != q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

🧠 How Devs Usually Mess This Up

If you’ve ever thought, “Let me just do an inorder or preorder traversal and compare the outputs,” congrats: you’ve missed the point. Traversals lie. Two distinct trees can produce the same sequence. That’s like comparing grocery lists written by two different chefs—one has eggs on the left, the other on the right, but the numbers match. Guess which one’s missing pancakes? Flattening the trees into arrays? That’s IKEA bookshelf logic. If your solution features more than one stack, walk away: recursion’s got you covered.

🔍 What’s Actually Going On

This is the binary tree polygraph test: visit every node in both trees at the same time. If one tree pulls a Houdini and produces a branch where the other doesn’t, it’s busted. If their values mismatch, also busted. The only way out unscathed is for every null/null, value/value, and branch/branch moment to match perfectly. Think buddy-cop movie, but every disagreement is an instant split-up.

🛠️ PseudoCode

• If both nodes are null: return true. (Both trees nap here; good sign.)
• If only one is null or values differ: return false. (Mismatch—case closed.)
• Recursively check the left children: isSameTree(p.left, q.left)
• Recursively check the right children: isSameTree(p.right, q.right)
• If both recursive checks return true, congratulations: these trees are secretly long-lost twins.

💻 The Code

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Traversal trap: Identical inorder/preorder doesn’t mean identical trees. Structure counts!
• Null nightmares: Don’t touch node.val before checking for null, unless you’re feeling lucky (or debugging for hours).
• Stack overflow: Huge trees + recursion = kaboom. But for most interview trees? You’re fine.
• O(n) time, O(h) space: Visit every node, stack maxes out at tree height. That’s as tidy as life gets.

🧠 Interviewer Brain-Tattoo

“Comparing tree traversals is like comparing two houses because the mailboxes are the same. Check every room.”