How is Subtree of Another Tree related to Same Tree?

subRoot is a subtree of root exactly when some node of root starts a tree that is the same as subRoot. So the solution is a DFS over root that calls the Same Tree check at each node.

What is the time complexity of Subtree of Another Tree?

O(m · n) in the worst case, where m and n are the sizes of the two trees: the Same Tree check can run up to n steps from each of the m nodes. Serializing both trees and using a string-matching algorithm such as KMP brings it to O(m + n).

Why is [3, 4, 5, 1, 2, null, null, null, null, 0] not a match for [4, 1, 2]?

A subtree must include all of a node's descendants. The node 4 in root has the extra 0 below its child 2, so the tree starting at 4 is not identical to subRoot.

Subtree of Another Tree

Check whether one binary tree appears as an exact subtree of another by running the Same Tree check from every node.

EasySolve on LeetCode

Problem Understanding

Subtree of Another Tree: given the roots of two binary trees root and subRoot, return true if some node of root has a subtree with exactly the same structure and values as subRoot. A subtree is a node together with all of its descendants.

Example: root = [3, 4, 5, 1, 2] and subRoot = [4, 1, 2] returns true: the tree under node 4 is [4, 1, 2].

The Intuition: Same Tree, From Every Node

The question breaks into two smaller ones:

Where could the match start? Any node of root. A DFS over root visits each one.
Does it match from here? That is exactly Same Tree: compare the tree at this node with subRoot, node by node.

So at each node: run the Same Tree check; if it passes, return true; otherwise search the left subtree, then the right. Both checks stop at the first difference.

Interactive Walkthrough

root and subRoot are drawn side by side. The node of root being tried as a starting point is outlined; inside each Same Tree check, the pair being compared is marked in both trees and a difference turns red. Rejected starting points fade, and the matching subtree turns green.

Dry Run Table

Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]

Start	Same Tree check	Result
3	3 ≠ 4	not here, search left
4	4 = 4, then 1 = 1, then 2 = 2, all children empty	match: return `true`

The right subtree of 3 is never searched, because the left one already returned true.

A Faster Approach

The check above is O(m · n) in the worst case. To do better, serialize both trees in preorder with markers for empty children (so that shape is kept), then test whether the subRoot string occurs in the root string with a linear-time string search such as KMP: O(m + n). In interviews the recursive version is the expected first answer; the serialization idea is a common follow-up.

The Solution Template

DFS over root, calling the Same Tree check at each node.

Subtree of Another Tree Code

1var isSubtree = function(root, subRoot) {
2    if (!root) {
3        return false;
4    }
5    if (isSame(root, subRoot)) {
6        return true;
7    }
8    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
9};
10
11function isSame(p, q) {
12    if (!p && !q) {
13        return true;
14    }
15    if (!p || !q || p.val !== q.val) {
16        return false;
17    }
18    return isSame(p.left, q.left) && isSame(p.right, q.right);
19}

Edge Cases & Common Mistakes

Extra descendants: a node whose values match subRoot but which has more children below is not a match; the Same Tree check catches it at the extra node.
Matching values at the wrong node: the first node with value 4 may fail while a later one matches, so the search must continue after a failed check.
Comparing only the root values: checking root.val == subRoot.val is not enough; the whole subtree must be identical.
Single-node subRoot: it matches any leaf with the same value, but not an internal node with that value.

Summary

Subtree of Another Tree is two DFS walks nested: an outer one that picks each node of root as a possible start, and the Same Tree check that compares from there. Both stop as soon as the answer is known.

More practice: DSA interview questions with answers · patterns cheat sheet

Balanced Binary Tree

Path Sum