#572 Subtree of Another Tree

frequently reported atMeta Amazon Google Microsoft

the problem

In plain words

You get two trees, root and subRoot. Return true if some node of root, together with everything below it, is an exact copy of subRoot — same shape, same values. root itself counts as one of its own subtrees.

in root = [3,4,5,1,2], subRoot = [4,1,2]

out true

Node 4 with children 1 and 2 is an exact copy.

in root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]

out false

Node 4 looks right at first, but its child 2 has an extra child 0 — a subtree takes everything below it.

1 ≤ nodes in root ≤ 2000
1 ≤ nodes in subRoot ≤ 1000
-10⁴ ≤ Node.val ≤ 10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (bottom-up)Group by a canonical key

where this runsGit stores every folder as a tree object named by the hash of its contents (including its sub-folders' hashes), so identical folders get the same id — subtree ids, with cryptographic hashes.

A subtree must match all the way down to the leaves. The simple way runs Same Tree from every node. The fast way gives every subtree shape an id — equal subtrees get equal ids — so each check becomes one int comparison.

solutions

From brute force to optimal

Walk root; at every node ask Same Tree whether the copy starts right there.

root == null → false.
isSame(root, subRoot) → true.
Otherwise try isSubtree(root.left) || isSubtree(root.right).

timeO(n·m) worst

Up to m comparisons at each of the n nodes — e.g. long chains of equal values that differ only at the bottom. Usually far less: isSame stops at the first difference.

spaceO(h₁ + h₂)

The outer recursion plus one Same Tree recursion on top of it.

javajava.util.*

1class Solution {2    public boolean isSubtree(TreeNode root, TreeNode subRoot) {3        if (root == null) return false;                         // ran out of places to start4        if (isSame(root, subRoot)) return true;                 // does the copy start right here?5        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);6    }7 8    /** LeetCode 100: same shape and same values. */9    private boolean isSame(TreeNode a, TreeNode b) {10        if (a == null || b == null) return a == b;11        return a.val == b.val && isSame(a.left, b.left) && isSame(a.right, b.right);12    }13}

Postorder: a subtree's shape is the triple (left id, value, right id). Each new triple gets the next id from a HashMap. Label subRoot first, then root with the same map; a node whose id equals subRoot's id starts an exact copy.

id(null) = 0.
key = id(left) + "," + val + "," + id(right).
id = ids.computeIfAbsent(key, k -> ids.size() + 1).
target = id(subRoot); label root; found as soon as some node's id == target.

timeO(n + m) expected

One postorder per tree; each node builds a short key from two ints and does one HashMap lookup (O(1) on average).

spaceO(n + m)

One map entry per distinct shape, plus the O(h) recursion stack.

javajava.util.*

1class Solution {2    private final Map<String, Integer> ids = new HashMap<>();   // shape "leftId,val,rightId" → its id3    private boolean found;4 5    public boolean isSubtree(TreeNode root, TreeNode subRoot) {6        ids.clear();7        found = false;8        int target = idOf(subRoot, -1);            // label subRoot first (-1: match nothing yet)9        idOf(root, target);                        // same map: an equal subtree gets the same id10        return found;11    }12 13    /** Postorder: a subtree's id depends only on (left id, value, right id). */14    private int idOf(TreeNode node, int target) {15        if (node == null) return 0;                // every empty subtree shares id 016        String key = idOf(node.left, target) + "," + node.val + "," + idOf(node.right, target);17        int id = ids.computeIfAbsent(key, k -> ids.size() + 1);      // new shape → next free id18        if (id == target) found = true;19        return id;20    }21}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private final Map<String, Integer> ids = new HashMap<>();   // shape "leftId,val,rightId" → its id3    private boolean found;4 5    public boolean isSubtree(TreeNode root, TreeNode subRoot) {6        ids.clear();7        found = false;8        int target = idOf(subRoot, -1);            // label subRoot first (-1: match nothing yet)9        idOf(root, target);                        // same map: an equal subtree gets the same id10        return found;11    }12 13    /** Postorder: a subtree's id depends only on (left id, value, right id). */14    private int idOf(TreeNode node, int target) {15        if (node == null) return 0;                // every empty subtree shares id 016        String key = idOf(node.left, target) + "," + node.val + "," + idOf(node.right, target);17        int id = ids.computeIfAbsent(key, k -> ids.size() + 1);      // new shape → next free id18        if (id == target) found = true;19        return id;20    }21}

in the room

How to say it in the interview

talk track

Start with the O(n·m) answer: it reuses Same Tree and is fine at these limits (2000 × 1000).
Then offer O(n + m): give every subtree an id from (left id, value, right id). Equal ids ⇔ equal subtrees, because the map compares whole keys — no collisions.
Mention the string way too: serialize both trees with null markers and separators, then search with KMP.

traps

Stopping at the first node whose value matches: that match can fail deep down while a later node matches. Keep searching.
Serializing with a comma only after each value: subRoot [2] becomes "2,#,#," and is found inside [12]'s "12,#,#,". Put a separator before every value too: ",12,#,#," can't contain ",2,#,#,".
Trusting plain hash codes of subtrees: two different subtrees can share a hash. The id map compares the full key, so it can't be fooled.

what they ask next

Follow-ups

Find all duplicate subtrees (LC 652)?

The same id map: count how many nodes get each id, and report one node for every id that appears a second time.

The string way?

Write both trees in preorder with # for null and a separator before every value, then look for subRoot's string inside root's. KMP makes that O(n + m); String.contains gives no linear-time guarantee.

before you submit

Edge cases to test

subRoot equals the whole tree → true.
A match that fails deeper down ([3,4,5,1,2,null,null,null,null,0]) → false.
Look-alike values: 12 must never match 2 (a string version needs separators).
Long chains of equal values: the O(n·m) worst case for the brute force.

practise next