572. Subtree of Another Tree

572

EasyTrees and Binary Search TreesNested DFS (traverse plus same-tree check)Subtree match by structural equality

Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a node in root such that the subtree rooted at that node is identical in structure and values to subRoot; otherwise return false.

Open official problem prompt ↗

In plain English

Decide whether the smaller tree appears verbatim as a complete branch of the larger tree.

Picture it like this

Scanning a family tree for a person whose entire line of descendants exactly matches a given smaller family tree, generation for generation.

Example

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Why: The subtree rooted at root's left child (4 with children 1 and 2) exactly matches subRoot.

Constraints

The number of nodes in root is in the range [1, 2000]The number of nodes in subRoot is in the range [1, 1000]-10^4 <= Node.val <= 10^4

Pattern lesson

See the pattern, then code

Subtree match by structural equality

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. At every node of root, ask whether the subtree there is identical to subRoot using a strict same-tree comparison. If any node passes, the answer is true.

New words, made simpleKnow these before the algorithm

Subtree: A node together with all of its descendants (never a partial fragment).
Structural equality: Two trees with identical shape and identical values at every corresponding position.
Anchor node: The node in root where the comparison with subRoot begins.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Best choiceNested DFS comparison

Simple and correct; fine for the given sizes and the standard interview answer.

Visit each node of root and test full-tree equality with subRoot from that node.

Time O(m*n)Space O(m)

Serialize and substring

Asymptotically faster but needs careful delimiters and value markers to avoid false matches; overkill here.

Serialize both trees with null markers and check whether subRoot's serialization is a substring of root's (using KMP for linear matching).

Time O(m+n)Space O(m+n)

The rule we keep true

Invariant

same(a, b) returns true iff the trees rooted at a and b are identical; isSubtree returns true iff some visited node of root anchors such an identity.

Why this is correct

Reasoning

A subtree match must be a full match starting at some node. By testing structural equality at every node of root, we cover all candidate anchors; the strict same-tree check (both null, or both non-null with equal values and matching children) guarantees no partial or shifted match is mistaken for a real one.

The algorithm in three movesSay these aloud before coding

1Write a helper that returns True only when two trees are identical (same shape and values)

compare root(3) vs subRoot(4): mismatch

2Traverse root node by node

compare node 4 vs subRoot 4: equal

3At each node, run the identity check against subRoot

children 1==1, 2==2 -> match

4Return True on the first match, else recurse into children

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readsame(3-tree, subRoot)

2 · Ask3 == 4?

3 · Update statevalues differ

4 · Resultnot a match; recurse

Key takeaway

The comparison anchors at root's node 4 and confirms every descendant matches subRoot.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-9Strict identity helper
Both empty is a match; exactly one empty or unequal values is a mismatch; otherwise recurse on both children.
2
Lines 10-13Base cases
An empty subRoot matches anything; an empty root cannot contain a non-empty subRoot.
3
Lines 14-16Anchor and recurse
Test equality here, then try the left and right children if this node is not a match.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

subRoot larger than root (cannot match)
Duplicate values that match structure only partially
root and subRoot identical (whole tree is the subtree)
Negative values

Common beginner mistakes

Only comparing node values without checking shape, accepting partial matches
Treating one-null-one-nonnull as equal
Confusing 'subtree' with 'subpath' or 'contains value'
Short-circuiting the same() check before verifying both children

Check your understanding

Why is checking value equality node-by-node during traversal not enough on its own?

PyPython 3 · solution.py

Optimal

1class Solution:2    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:3        def same(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:4            if not a and not b:5                return True6            if not a or not b or a.val != b.val:7                return False8            return same(a.left, b.left) and same(a.right, b.right)9        if not subRoot:10            return True11        if not root:12            return False13        if same(root, subRoot):14            return True15        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Time complexityO(m*n)Optimized

Space complexityO(m)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaApple

Subtree of Another Tree

Subtree of Another Tree

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees