LeetCode · #572

Subtree of Another Tree Solution

Given two trees root and subRoot, return true if subRoot is a subtree of root.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #572

🏗️

Pattern

Recursion — isSameTree at every node

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 of subRoot, and false otherwise.

Example

 Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true // The subtree rooted at node 4 matches subRoot exactly 

Constraints

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

Section Two · Approach 1

Serialize & String Match — O(m + n)

Serialize both trees with null markers, then check if subRoot's string is a substring of root's string. O(m+n) with KMP but tricky — need careful null markers to avoid false matches like "12" matching "2".

Section Three · Approach 2

Recursive — isSameTree at Every Node — O(m · n)

At each node in root, check if the subtree rooted there is identical to subRoot (using LC 100 Same Tree). If any match → true. If no node matches → false.

💡 Mental model: You have a photo (subRoot) and a building (root). Walk through every room in the building and try to match the photo. If any room's layout matches the photo exactly → found the subtree.

Algorithm

Base: If root is null → false. If subRoot is null → true (null is subtree of anything).
Check: If isSameTree(root, subRoot) → true.
Recurse: isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot).

Section Four · Trace

Visual Walkthrough

Check isSameTree at each node of root

Section Five · Implementation

Code — Java & Python

Java — Recursive

 class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
private boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null || p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Python — Recursive

 class Solution:
def isSubtree(self, root, subRoot) -> bool:
if not root: return False if self.isSameTree(root, subRoot): return True return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def isSameTree(self, p, q) -> bool:
if not p and not q: return True if not p or not q or p.val != q.val: return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Recursive	O(m · n)	O(h)
Serialization + KMP	O(m + n)	O(m + n)

m = nodes in root, n = nodes in subRoot.:

In the worst case, we check isSameTree (O(n)) at every node of root (O(m)) → O(m·n).
For most interview problems, this is acceptable.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Same tree	`root == subRoot`	isSameTree at root → true immediately.
Leaf subtree	`subRoot = [2]`	Single-node match — must be a leaf in root (no extra children).
Partial match	`root=[1,2,3], sub=[1,2]`	Root has extra child (3) that subRoot doesn't → false at root. But check deeper nodes.

⚠ Common Mistake: Confusing "subtree" with "substructure." A subtree must match from the given node downward including all leaves. If root has [4,1,2,0] and subRoot is [4,1,2], it's false because node 1 has an extra child 0 in root.

← Back to Trees problems

LearningTree

LC 572 · Subtree of Another Tree — Solution & Explanation | DSA Guide