Solution

You'll decide whether one binary tree appears, intact and complete, somewhere inside another — and the whole problem turns on what "intact and complete" really means.

The problem, in plain English

Imagine subRoot is a small shape stamped on a transparent sheet, and root is a big tree drawn on paper. You slide the sheet over every node of the big tree and ask: does the shape line up exactly here — same nodes, same values, same left/right arrangement, and nothing extra poking out below? If it lines up at even one node, the answer is true. The catch beginners trip over: the match has to extend all the way down to the leaves. A piece of subRoot showing up "in the middle" of root, with more nodes hanging beneath it, does not count.

So the problem has two layers. The outer layer is a traversal: visit every node of root as a potential starting point. The inner layer is a deep equality check: standing at one node, ask "is the entire tree rooted here identical to the entire subRoot?" Get either layer wrong and you get subtle false positives.

The mental model

Split the problem in two and the whole thing falls out:

1. sameTree(a, b) — a helper that returns true only if the two trees are structurally identical: same shape, same values, everywhere. This is the deep-equality check.
2. A walk over root — at every node n, call sameTree(n, subRoot). If any node returns true, root contains subRoot.

The hard half is sameTree. Two trees are identical when three things hold at every level: the current values are equal, the left subtrees are identical, and the right subtrees are identical. That last sentence is recursive on purpose — "identical left subtrees" is just sameTree applied one level down.

A first attempt

The natural first instinct is to forget the deep check entirely and search for the value. "Find a node whose value matches subRoot's root value — if it's there, the subtree must be there too." That gives a value-only contains check:

function binaryTreeSubtreeNaive(root, subRoot) {
  if (subRoot === null) return true;
  if (root === null) return false;
  // Wrong idea: a matching value somewhere means a match.
  if (root.val === subRoot.val) return true;
  return (
    binaryTreeSubtreeNaive(root.left, subRoot) ||
    binaryTreeSubtreeNaive(root.right, subRoot)
  );
}

This says true the moment it spots a node whose value equals subRoot.val. But a shared value tells you almost nothing. Take root = { 4, left: 1, right: 2 } and subRoot = { 4, left: 9, right: 9 }. The naive version sees a 4 in root, returns true, and is dead wrong — the children 1, 2 don't match 9, 9 at all. It checked one value and ignored the entire shape below.

A close cousin of this bug is a botched sameTree that mishandles null. Authors often write the equality check so that reaching a null on one side "passes":

function sameTreeBad(a, b) {
  if (a === null || b === null) return true; // BUG: treats "one side ran out" as a match
  return (
    a.val === b.val &&
    sameTreeBad(a.left, b.left) &&
    sameTreeBad(a.right, b.right)
  );
}

Here, if a is a leaf (a.left === null) but b still has a left child, the recursion hits a.left === null, returns true, and silently accepts trees of different shapes. The picture below is exactly this case — agreement at the top, a difference deep down that a sloppy null check would wave through.

The working solution

Two correct functions: a deep-equality sameTree, and a traversal that calls it at every node.

function binaryTreeSubtree(root, subRoot) {
  // An empty pattern is a subtree of everything (documented policy).
  if (subRoot === null) return true;
  // Nothing left to search, and the pattern is non-empty → no match.
  if (root === null) return false;

  // Does the subtree rooted HERE equal subRoot? If so, we're done.
  if (sameTree(root, subRoot)) return true;

  // Otherwise try every other node as a starting point.
  return (
    binaryTreeSubtree(root.left, subRoot) ||
    binaryTreeSubtree(root.right, subRoot)
  );
}

// Deep structural equality: same shape AND same values, everywhere.
function sameTree(a, b) {
  // Both ran out at the same place → the shapes line up here.
  if (a === null && b === null) return true;
  // Exactly one is null → shapes differ; not equal.
  if (a === null || b === null) return false;
  // Values must match, AND both child pairs must be equal.
  return (
    a.val === b.val &&
    sameTree(a.left, b.left) &&
    sameTree(a.right, b.right)
  );
}

module.exports = { binaryTreeSubtree };

The shift from the naive version is the swap of root.val === subRoot.val for sameTree(root, subRoot). Instead of asking "does this node's value match?", we ask "does this node's entire subtree match?". That single change moves us from a value-contains check to a true structural-subtree check.

The order of the three null checks inside sameTree is the load-bearing part. The "both null" check comes first so two trees that end at the same place agree. The "exactly one null" check comes second so a leaf on one side and a node on the other are correctly rejected — this is precisely the bug the naive sameTreeBad had. Only after both null cases are handled do we compare a.val and recurse; by then both a and b are guaranteed non-null, so reading a.val and a.left is safe.

Walking through one call

Trace binaryTreeSubtree(root, subRoot) on the tree from the first diagram. root is 3 → (4 → (1, 2), 5) and subRoot is 4 → (1, 2).

binaryTreeSubtree(node 3, subRoot)
  subRoot not null, root not null
  sameTree(node 3, subRoot 4)?
    a.val 3 === b.val 4 ?  no  → false
  not a match here. Recurse left, then right.

  binaryTreeSubtree(node 4, subRoot)       ← the promising node
    sameTree(node 4, subRoot 4)?
      a.val 4 === b.val 4 ?  yes
      sameTree(node 1, subRoot.left 1)?
        a.val 1 === b.val 1 ?  yes
        sameTree(null, null) → true        (both left children absent)
        sameTree(null, null) → true        (both right children absent)
        → true
      sameTree(node 2, subRoot.right 2)?
        a.val 2 === b.val 2 ?  yes
        sameTree(null, null) → true
        sameTree(null, null) → true
        → true
      4 === 4  AND  left true  AND  right true  → true
    sameTree returned true → binaryTreeSubtree returns true

The outer walk reaches node 4, hands it to sameTree, and sameTree descends both children to their leaves, confirming every value and every shape. Because the || short-circuits, the moment node 4 reports a match we stop — we never even look at node 5. Had we instead used the buggy value-only check, we'd have returned true back at node 3's descendants without ever verifying the 1 and 2 below.

Now contrast the embedded-fragment trap. If subRoot were a single leaf 2, then at a root node valued 2 that has children, sameTree(node 2-with-children, leaf 2) compares 2 === 2 (yes) but then sameTree(node 3, null) hits "exactly one null" and returns false. The fragment is embedded, but the extra children sink the match — exactly the contract we want.

Gotchas

• A partial / embedded match is not a subtree. Finding subRoot's shape inside root with extra nodes hanging below the bottom of the pattern does not count. The fix is baked into sameTree: when the pattern hits null but root still has a node there, "exactly one null → false" rejects it. Don't loosen that check to "ignore extra nodes."
• null handling in sameTree must be exact. Both null → equal (the shapes ended together). Exactly one null → not equal (one tree ran out before the other). If you collapse these into a single if (!a || !b) return true, you accept trees of different shapes — the bug in sameTreeBad above. Check "both null" before "one null."
• Shape AND value, not value alone. A node in root whose value equals subRoot.val is only a candidate. The naive root.val === subRoot.val check returns true on the first value collision and ignores everything below. Always run the full sameTree from that candidate.
• You must try every node, not just the first value hit. binaryTreeSubtree recurses into both root.left and root.right even when sameTree fails at the current node, because the real match might start deeper. Stopping at the first node whose value matches subRoot.val misses matches that begin lower in the tree.
• Duplicate values are a trap for value-only thinking. When the same value appears at many nodes, the first one you reach is rarely the one that matches all the way down. You can only confirm a match by running sameTree at each candidate; a value match alone is meaningless when values repeat.
• Decide and document the empty-subRoot policy. Here, subRoot === null returns true (an empty tree is a subtree of everything, including an empty root). Some interviewers prefer false or "undefined." Pick one, put the check at the very top of binaryTreeSubtree, and state it — silent disagreement on this edge case is a common interview miscommunication.

Going further

• Serialize and substring-search. Flatten both trees into strings with explicit null markers (e.g. preorder with # for null and a leading delimiter on each value), then ask whether serialize(subRoot) is a substring of serialize(root). The null markers and value delimiters are essential — without them, a value 12 and the pair 1, 2 can collide, and an embedded fragment can falsely "match." This trades the O(m × n) worst case of node-by-node comparison for roughly O(m + n) string work, at the cost of building two strings.
• Hashing / Merkle trees. Give every node a hash computed from its value and its children's hashes (a Merkle tree). Then "is subRoot a subtree" becomes "does subRoot's root hash appear among root's node hashes?" — an O(n) set lookup after an O(n) preprocessing pass. Watch for hash collisions: a robust version re-runs sameTree on a hash hit to confirm.
• KMP on the serialization. The substring approach above can use naive string search (String.prototype.includes), but on adversarial inputs that degrades. Running Knuth–Morris–Pratt on the serialized arrays guarantees linear O(m + n) matching regardless of input shape — the textbook way to make the serialize-and-search approach worst-case optimal.