Subtree of Another Tree

The problem

Given roots root and subRoot, return true if root contains a subtree with the same structure and node values as subRoot.

root:        subRoot:
    3            4
   / \          / \
  4   5        1   2
 / \
1   2
→ true

A subtree must include all descendants of that node — not a partial shape.

Node shape

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

Brute force: for every node, isSameTree

function isSameTree(a: TreeNode | null, b: TreeNode | null): boolean {
  if (!a && !b) return true;
  if (!a || !b || a.val !== b.val) return false;
  return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
}

function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  if (!subRoot) return true;
  if (!root) return false;
  if (isSameTree(root, subRoot)) return true;
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

Time	O(m · n) worst — m, n node counts
Space	O(h)

Optimal-ish: serialization + string find

Serialize with null markers and separators so values don’t glue ("12" vs "1","2"). Check if sub serialization is substring of root serialization. Average fast; worst still related to string match.

function serialize(node: TreeNode | null): string {
  if (!node) return "#,";
  return `^${node.val},${serialize(node.left)}${serialize(node.right)}`;
}

function isSubtreeSerial(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  return serialize(root).includes(serialize(subRoot));
}

The ^ prefix avoids false positives like matching 2 inside 12 when combined with commas carefully — markers matter.

For interviews, the double DFS is clearer and enough unless they ask to optimize.

Edge cases

• subRoot null → true (empty subtree)
• root null, sub non-null → false
• Values match but structure differs
• Multiple candidate roots with same value

Common bugs

• Checking only values along a path
• Allowing non-contiguous “subtree”
• Serialization without nulls

Interview delivery

1. Define subtree strictly.
2. isSameTree helper.
3. Walk every node in root.
4. O(mn).
5. Mention serialize optimization.

Related

• Same Tree
• Maximum Depth of Binary Tree
• Serialize Deserialize Binary Tree
• Lowest Common Ancestor BST

Complexity honest take

Worst case every node value equals subRoot.val, so you run full isSameTree often → O(m·n). Average case much better when values vary. Interviewers rarely need the serialization+KMP optimization unless they push.

Serialization false positives

If you serialize as concatenated values without separators, 12 matches inside 1 and 2 poorly… actually 12 as subtree of values 1 and 2 is the classic bug. Use delimiters and null markers: ^val,.

Definition of subtree

Must be a node plus all its descendants. A “partial” matching shape that ignores some children is not a subtree for this problem.

Further reading

• LeetCode 572 — Subtree of Another Tree
• Tree traversal