Difficulty: EasyTrees

Subtree of Another Tree

Problem in Plain English

Given two binary trees called root and subRoot, decide whether root contains a subtree with exactly the same structure and node values as subRoot. A subtree is a node together with all of its descendants, and the whole tree counts as a subtree of itself.

Problem Statement

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values as subRoot, and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree itself is also considered a subtree of tree, so identical trees are a match.

Constraints

The tree root contains between 1 and 2000 nodes.
The tree subRoot contains between 1 and 1000 nodes.
Node values lie between $-10^4$ and $10^4$ , inclusive.
Inputs are nonempty ordinary binary trees with no cycles or shared children inside either tree. Array examples use level order with null for a missing child.

Examples

Example 1

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

The node with value 4 in root has children 1 and 2, exactly matching subRoot.

Example 2

Input: root = [4], subRoot = [4]
Output: true

The entire single-node tree is a valid subtree. Its value and both absent child slots match.

Example 3

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

The candidate node 4 looks right, but its child 2 has an extra child 0, so the structures differ.

Example 4

Input: root = [1,1,null,2], subRoot = [1,2]
Output: true

The first 1 fails because its left child is 1, not 2. The second 1 has exactly the left child 2, so searching must continue after a failed candidate.

Intuition

Separate finding a candidate root from proving an exact match. In Example 1, 3 cannot match target root 4, but its left child 4 can: every descendant and missing child agrees. A candidate with an extra descendant fails because a subtree includes all descendants; you cannot prune it to fit the target.

Approaches

Check Every Node

Solution Details

Reveal Check Every Node: intuition, complexity, and code

Intuition

Visit every possible starting node and compare its entire subtree with the target. A stack searches candidate roots; a separate stack compares corresponding node pairs, including missing children. This direct method can repeat much of the target comparison at many candidates, but explicit stacks handle 2000-node chains without recursive call limits.

Step-by-Step Logic

For Example 1, initialize the candidate stack with [3] and keep target root 4 fixed.
Pop 3: its value differs from 4, so the equality check fails immediately. Push right child 5, then left child 4; the left candidate is processed next.
Pop 4 and compare (4,4). Push the right pair (2,2) and then the left pair (1,1).
Compare (1,1) and both pairs of missing children; then compare (2,2) and both pairs of missing children. Every pair agrees.
The pair stack empties, so return true. Candidate 5 remains unvisited because a single exact match is enough.

Why It Works

The candidate stack begins with the root and, after any failed comparison, adds both existing children. Thus every possible subtree root is eventually tested unless a match has already been found. The comparison stack preserves corresponding left/right positions. It succeeds only after all pairs agree in both presence and value, so it certifies an exact whole-subtree match. Returning true is therefore sound, and exhausting every candidate without a match proves none exists.

Dry Run

Check Every Node: variable states at each step
action	candidate stack (top at right)	comparison stack (top at right)	result / transition
initialize	`[3]`	`[]`	target root remains `4`
pop candidate `3`	`[]`	`[(3,4)]`	values differ; comparison returns `false`
push children of `3`	`[5,4]`	`[]`	push right before left
pop candidate `4`	`[5]`	`[(4,4)]`	comparison pending
pop `(4,4)`	`[5]`	`[(2,2),(1,1)]`	equal; append right and left pairs
pop `(1,1)`	`[5]`	`[(2,2),(null,null),(null,null)]`	equal; append both missing slots
pop first missing pair	`[5]`	`[(2,2),(null,null)]`	both missing; skip
pop second missing pair	`[5]`	`[(2,2)]`	both missing; skip
pop `(2,2)`	`[5]`	`[(null,null),(null,null)]`	equal; append both missing slots
pop first missing pair	`[5]`	`[(null,null)]`	both missing; skip
pop second missing pair	`[5]`	`[]`	both missing; skip
comparison stack empty	`[5]`	`[]`	equality succeeds; final answer `true`

Complexity Analysis

Time Complexity

O(m n)

Space Complexity

O(h_r + h_s)

Let m and n be the node counts of root and subRoot, and h_r and h_s their heights. At most m candidates each compare O(n) positions, including null slots. Repeated equal-valued chains with a late mismatch realize the quadratic worst case. The candidate DFS stack holds O(h_r) pending siblings. The pair DFS stack holds O(h_s) pending pairs: descent continues only while both nodes exist. Both stacks coexist, so their live storage adds; each comparison stack is discarded before the next candidate. Up to O(m n) pair arrays/tuples are allocated over the entire run, but only O(h_r + h_s) are live at once. Input nodes are never copied or mutated.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Deque;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8}9
10class Solution {11    public boolean isSubtree(TreeNode root, TreeNode subRoot) {12        Deque<TreeNode> candidates = new ArrayDeque<>();13        candidates.push(root);14        while (!candidates.isEmpty()) {15            TreeNode node = candidates.pop();16            if (same(node, subRoot)) return true;17            // LIFO: push right before left so the left candidate is visited first.18            if (node.right != null) candidates.push(node.right);19            if (node.left != null) candidates.push(node.left);20        }21        return false;22    }23
24    private boolean same(TreeNode p, TreeNode q) {25        Deque<TreeNode[]> pairs = new ArrayDeque<>();26        pairs.push(new TreeNode[]{p, q});27        while (!pairs.isEmpty()) {28            TreeNode[] pair = pairs.pop();29            TreeNode a = pair[0], b = pair[1];30            if (a == null && b == null) continue;31            if (a == null || b == null || a.val != b.val) return false;32            // Null slots are compared too; an extra descendant invalidates a match.33            pairs.push(new TreeNode[]{a.right, b.right});34            pairs.push(new TreeNode[]{a.left, b.left});35        }36        return true;37    }38}

Hints

Hint 1

First distinguish an exact subtree comparison from a search for where that comparison should start.

Hint 2

When a candidate fails, search its children; a repeated root value may match farther down.

Hint 3

Preorder tokens need explicit missing-child markers. Match whole tokens to avoid multi-digit value collisions.

Hint 4

Use a prefix table for KMP so failed partial matches reuse compatible suffixes instead of starting from scratch.

Edge Cases

A one-node root equals the one-node target: the whole tree qualifies, as in Example 2.
The candidate has an extra descendant, as in Example 3: matching visible values is insufficient.
Repeated root values require continuing after failure, as in Example 4.
A target larger than root cannot match; both methods return false without special size logic.
A 2000-node chain should be processed with explicit stacks; ordinary recursive Python helpers can exceed the default recursion limit.
Value 2 must not match within 12, and negative values must remain distinct whole tokens.

Common Mistakes and Interview Tips

Checking only the main root and returning false when its value differs from the target root.
Returning true after a root value match, or using OR instead of AND for corresponding child equality.
Allowing a candidate to have extra children because the target has no node in that position.
Dropping null markers from serialization loses structure; [1,2] and [1,null,2] then have the same value visits.
Claiming built-in contains/includes guarantees a linear scan; explicit KMP establishes the bound shown here.
On a KMP mismatch, setting j to zero skips reusable suffixes; use lps[j - 1] until the next token is compatible.
Using recursive serialization on the maximum chain without accounting for language stack limits.

Key Takeaway

A structural search can be reduced to sequence matching when the encoding is unambiguous and each candidate occupies a contiguous block. Keep missing-child markers, compare whole tokens, and use a proven linear matcher to remove repeated work.