The O(n) Club: Subtree of Another Tree: How to Find Doppelgänger Branches (and Not Lose Your Mind)

The O(n) Club: Subtree of Another Tree – How to Find Doppelgänger Branches (and Not Lose Your Mind)

⚡ TL;DR

Want to know if subRoot is actually a fully-formed stunt double in root? Don’t just match numbers—make sure all the lefts, rights, and awkward middles match too. Brute force it by checking at every node. The party trick is these two recursive frenemies:

// Java snippet (abridged)
boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    if (isSameTree(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

🧠 How Devs Usually Mess This Up

The rookie move? Glance at root values and say, “close enough.” Or treat this as a list problem: maybe subRoot’s preorder traversal lives inside root’s. Nope. You aren’t looking for scattered lucky numbers—you want the whole shape, every left and right, to line up like synchronized swimmers.

If you confuse a subtree with a subsequence, you might as well compare a burger to a sushi roll because they both have rice.

🔍 What’s Actually Going On

Imagine your job is to spot a bonsai impersonating part of a big oak. You hike around every possible branch in root—at each node, you squint and ask, “Hey, does this mini-tree exactly match my subRoot?” If yes, congrats, you’re done. If not, keep stomping through the underbrush (a.k.a. left and right children) until the sun sets or you run out of nodes.

This is classic recursive DFS. At each step: check for an identical tree. If you find it, celebrate. Otherwise, keep digging. No need to overthink—unless you’re into serializing everything just to annoy future-you.

🛠️ PseudoCode

• For each node in root:
  • Check if the tree from here is identical to subRoot.
• To check “identical”:
  • If both nodes are null: they match. (Empty pockets are still pockets, right?)
  • If one’s null but the other’s not: fail.
  • If values differ: fail. No body doubles allowed.
  • Recurse on left and right children—repeat existential check.
• If identical at any node: return true. Else: keep trudging.