572. Subtree of Another Tree

Quick Identifier

• Topic: trees
• Pattern: Tree DFS + isSame pattern
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Microsoft, Apple
• Frequency: High
• LeetCode: 572

Quick Sights

• Time Complexity: O(n * m) from the optimal approach.
• Space Complexity: O(h) from the optimal approach.
• Core Mechanism: Given roots of two binary trees root and subRoot, return true if subRoot is a subtree of root—that is, there exists some node in the first tree such that the subtree rooted there is identical to subRoot (structure and values).

Concept Explanation

Given roots of two binary trees root and subRoot, return true if subRoot is a subtree of root—that is, there exists some node in the first tree such that the subtree rooted there is identical to subRoot (structure and values).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• "Subtree of another tree"
• Must match entire subRoot, not only a path
• Often two helpers: “are these trees the same?” and “search for match”

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(n * m) worst case — at every node of root, run full same-tree check (acceptable for interview).
• Better — string serialization + KMP — O(n+m) theoretically — heavy to implement under time pressure.
• Optimal (interview) — O(n * m) time / O(h) stack — DFS: isSubtree if current matches subRoot via isSameTree, else recurse left/right.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
	if root == nil {
		return subRoot == nil
	}
	return isSameTree(root, subRoot) ||
		isSubtree(root.Left, subRoot) ||
		isSubtree(root.Right, subRoot)
}

func isSameTree(primary *TreeNode, secondary *TreeNode) bool {
	if primary == nil && secondary == nil {
		return true
	}
	if primary == nil || secondary == nil {
		return false
	}
	if primary.Val != secondary.Val {
		return false
	}
	return isSameTree(primary.Left, secondary.Left) && isSameTree(primary.Right, secondary.Right)
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function isSubtree(root, subRoot) {
	if (root === null) {
		return subRoot === null;
	}
	return (
		isSameTree(root, subRoot) ||
		isSubtree(root.left, subRoot) ||
		isSubtree(root.right, subRoot)
	);
}

function isSameTree(primary, secondary) {
	if (primary === null && secondary === null) {
		return true;
	}
	if (primary === null || secondary === null) {
		return false;
	}
	if (primary.val !== secondary.val) {
		return false;
	}
	return (
		isSameTree(primary.left, secondary.left) &&
		isSameTree(primary.right, secondary.right)
	);
}

Walkthrough

root = 3/4,5 / 1,2, null,null,0 and subRoot = 4/1,2

Invariant: isSameTree is the exact 100. Same Tree check; isSubtree ORs a match at the current node with success in children.

Edge Cases

• subRoot empty: LeetCode often defines empty as subtree of any tree (read statement; usually true).
• Single-node subRoot — must find equal value node with two nil children if subRoot is a leaf.

Pitfalls

• Confusing path embed with subtree embed (subtree needs full left/right match under the chosen node)
• Short-circuiting: need isSame before diving, not only at leaves

Similar Problems

• 100. Same Tree — the isSameTree building block.
• 104. Maximum Depth of Binary Tree — simpler single-tree traversal.
• 235. Lowest Common Ancestor of a BST — another “find special node in tree” story.

Variants

• Count how many times subRoot appears as a subtree.
• Merkle hash on subtrees to avoid O(n*m) in very large static trees.

Mind-Map Tags

#trees #dfs #subtree #same-tree-helper #or-recursion