LeetCode 572 · Easy · Trees

Subtree of Another Tree

Given two binary trees root and subRoot, decide whether some node of root starts a subtree identical to subRoot: same shape, same values, all the way down to the leaves.

O(m·n)time
O(h)space · call stack
DFS + Same Treetry every node as the anchor

level order, null = no child · root 1 to 15 nodes, 4 levels · subRoot 1 to 7 nodes · values −99 to 99

root badge = sameTree from this node

subRoot

isSubtree frames one per anchor tried · newest on the right

sameTree frames pairs s,t walked in lockstep · N = null

public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (subRoot == null) { return true; } if (root == null) { return false; } if (sameTree(root, subRoot)) { return true; } return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}private boolean sameTree(TreeNode s, TreeNode t) { if (s == null && t == null) { return true; } if (s != null && t != null && s.val == t.val) { return sameTree(s.left, t.left) && sameTree(s.right, t.right); } return false;}
root
—
s, t
—
sameTree
—
anchors tried
0
return
—

Why it works

  1. The brute force is the solution here. Any match must start at some node of root, so try every node as an anchor and run Same Tree from it: O(m·n) in the worst case, where most anchors fail on the first compare.
  2. Same Tree is strict. A match must line up null for null too, so subRoot has to end exactly where the anchored subtree ends. Matching only the top few levels is not enough (Ex 2).
  3. Cost: isSubtree visits each of the n nodes once; each visit may run a Same Tree walk of up to m pairs. The two stacks together are at most O(h) deep.
  4. Pitfall: stopping at the first anchor whose value matches. In "near misses first" the first few 1s look right and fail lower down; the search must go on to the other anchors.
  5. Faster: serialize both trees with null markers and run a string search (KMP or hashing) for O(m + n). Wrap every value in separators so 2 does not match inside 12.