572. Subtree of Another Tree

At a Glance

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

Problem (one-liner)

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).

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”

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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