Blind 75 Visualized

#31 · Trees

Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if some node of root together with ALL of its descendants is identical to subRoot.

EasyLeetCode
  • Current node
  • On the path / call stack
  • Done / found
  • Rejected
  • Temporary thread (Morris)
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary tree + "same tree" check

A subtree is a node together with every descendant. So the question is: is there a node of root at which "same tree" with subRoot holds? The cheap part is the equality test; the cost is how many nodes you must test.

Memory layout

Pointer-linked nodes. The tests use only recursion depth as extra space.

OperationCost
same-tree check at one nodeO(min(size, m))
try every nodeO(n·m) worst case

Canonical encodings (serialization, subtree ids)

A tree can be turned into text (pre-order with markers) so that identical subtrees give identical text, making "is a subtree" the same as "is a substring". Better still, hash-consing assigns each distinct shape a unique integer id, making the check an integer comparison with no collisions.

Memory layout

A string of O(n) characters, or a table of O(n) distinct (leftId, value, rightId) keys.

OperationCost
serialize + substringO(n + m) to build; O(n·m) naive search, O(n + m) with KMP
subtree idsO(n + m) expected, exact

Why it fits

  • Any node of root could be the match, so every node has to be considered, but most can be rejected in O(1) (different value or different height).
  • Height is a cheap invariant: two identical subtrees must have the same height, so only nodes with height equal to subRoot's need a full comparison.
  • Encoding each subtree as one comparable object (a string or an integer id) turns "compare two trees" into "compare two values", which makes the whole problem linear.

Why alternatives degrade

Compare pre-order sequences without empty markers:
Different trees can share the same sequence of values, and without delimiters 12 and 1,2 look alike: false positives.
Look only for a node with the same value as subRoot.val:
Values repeat, and a matching root does not mean the whole subtree matches (the descendants must also be identical).
Hashing subtrees with a numeric hash:
Can collide and give a wrong answer. Hash-consing with exact keys avoids this.

Four approaches, from naive to production

1 · beginner

Try "same tree" at every node

time O(n·m)space O(h)

Walk the nodes of root. At each node run the same-tree check against subRoot; if it succeeds, return true.

bool isSame(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b || a->val != b->val) return false;
    return isSame(a->left, b->left) && isSame(a->right, b->right);
}

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (!root) return false;
    if (isSame(root, subRoot)) return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

Flaws & bottlenecks

  • Re-compares overlapping regions: in the worst case (every value equal) each of n nodes triggers an O(m) comparison.
  • Does a full recursive comparison even where the first values already differ in height or size.
  • Recursion depth is the height of root plus the height of the comparison.

Interviewer cross-questions

What is the worst case input?

Say: A long chain of equal values in root and a slightly different chain in subRoot (for example all 1s with a different value at the end): every node starts a long comparison that fails only at the last step: O(n·m).

How can you skip most comparisons?

Say: Compare heights first: a node whose height differs from subRoot's cannot match. Or encode every subtree as a comparable id.

Why must the comparison go all the way down?

Say: A subtree must include ALL descendants. If root had an extra child below a matching leaf, the trees would differ, which only a complete comparison catches.

2 · intermediate

Serialize both, search the text

time O(n·m) naive searchspace O(n + m)

Write both trees as pre-order strings with markers for empty children, and check whether the second string occurs inside the first.

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    function<string(TreeNode*)> ser = [&](TreeNode* n) -> string {
        return n ? "^" + to_string(n->val) + "," + ser(n->left) + "," + ser(n->right) : "#";
    };
    return ser(root).find(ser(subRoot)) != string::npos;
}

Flaws & bottlenecks

  • The naive substring search is O(n·m) in the worst case (use KMP or Z-function for linear).
  • Needs both the "^" prefix and the "#" marker: dropping either causes false positives (e.g. "12" contains "2").
  • Builds large intermediate strings.

Interviewer cross-questions

What goes wrong without the "^" prefix?

Say: Substring matching would find "2" inside "12". The prefix marks the start of a value so a match must begin at a node boundary.

Why are the "#" markers needed?

Say: They record missing children. Without them a left-leaning and a right-leaning tree with the same values could produce the same string, and a leaf could match a node that has children.

How do you make the search linear?

Say: Run KMP (or the Z-algorithm) on the two strings instead of the naive includes: O(n + m).

3 · advanced

Heights prune the comparisons

time O(n + k·m)space O(h)

Compute heights bottom-up. Only when a node's height equals the height of subRoot do we run the same-tree comparison.

int height(TreeNode* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }

bool isSame(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b || a->val != b->val) return false;
    return isSame(a->left, b->left) && isSame(a->right, b->right);
}

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    int target = height(subRoot);
    bool found = false;
    function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int h = 1 + max(dfs(node->left), dfs(node->right));
        if (h == target && isSame(node, subRoot)) found = true;
        return h;
    };
    dfs(root);
    return found;
}

Flaws & bottlenecks

  • Still O(n·m) in the worst case (many nodes with the same height as subRoot).
  • Three functions to keep consistent (dfs, height, isSame).
  • Height equality is necessary but not sufficient, so the full comparison is still needed.

Interviewer cross-questions

Why can a node of the wrong height be skipped?

Say: Identical trees have identical heights. If the node is taller or shorter than subRoot, it cannot be equal, so no comparison is needed.

How many nodes can share one height?

Say: At most about n / 2^(h−1) nodes can have height h in the worst case, so the number of full comparisons (k) is often small, though adversarial input can make it large.

Could you also compare sizes?

Say: Yes: node count is another necessary invariant. Combining height, size and value makes false candidates rarer, but only exact encodings give a guaranteed linear bound.

4 · expert

Subtree ids by hash-consing

time O(n + m)space O(n + m)

Give each subtree an integer id from the exact triple (left id, value, right id), reusing the id when the triple was seen before. Identical subtrees share an id, so "subRoot occurs in root" is "some node of root has subRoot's id".

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    map<string, int> ids;
    bool found = false;
    int target = -1;
    function<int(TreeNode*)> idOf = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int l = idOf(node->left);
        int r = idOf(node->right);
        string key = to_string(l) + "," + to_string(node->val) + "," + to_string(r);
        if (!ids.count(key)) { int nid = ids.size() + 1; ids[key] = nid; }
        int id = ids[key];
        if (id == target) found = true;
        return id;
    };
    target = idOf(subRoot);
    idOf(root);
    return found;
}

Flaws & bottlenecks

  • Needs O(n + m) memory for the table of keys.
  • Builds a string key per node (cost proportional to the key length), which is fine here because keys are short, but the table is a hash map with its own overhead.
  • More conceptually demanding than the simple solutions, so harder to explain.

Interviewer cross-questions

Why are there no collisions?

Say: The key is the exact tuple (left id, value, right id), not a hash of it. Two subtrees get the same id only if their children have the same ids and the values are equal, which by induction means they are structurally identical.

What is the complexity?

Say: Each node is processed once with an O(1) table lookup on a short key: O(n + m) time and space.

Where else is this idea used?

Say: It is "hash-consing" (also used in compilers to deduplicate expressions and in tools like Merkle trees and DAG compression): equal subtrees are stored once, so equality is an id comparison.

Synchronized code walkthrough

Showing: Try "same tree" at every node — shares the player above; click any step to jump.

bool isSame(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b || a->val != b->val) return false;
    return isSame(a->left, b->left) && isSame(a->right, b->right);
}

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (!root) return false;
    if (isSame(root, subRoot)) return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}