Subtree of Another Tree

Try every node in root as a candidate root

time O(n * m)space O(h)

A subtree match isn't 'subRoot's value appears somewhere' — it's isSameTree at some candidate node, checked all the way down to matching null boundaries. isSubtree tries every node of root, in preorder, as that candidate: if isSameTree(candidate, subRoot) succeeds the search stops, otherwise it continues into the candidate's own children.

Details

Animated on: Does root = [3,4,5,1,2] contain a subtree that matches subRoot = [4,1,2] exactly? Expected true.

Problem:Subtree of Another TreeEasy

Try every node in root as a candidate root

step 1 / 12

root | subRoot

Call stack

isSubtree(3)

Try node 3 as a candidate: call isSameTree(3, subRoot).

Pseudocode

1FUNCTION isSubtree(root, subRoot):
2  IF root = null:  RETURN false
3  IF isSameTree(root, subRoot):  RETURN true
4  RETURN isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot)
5FUNCTION isSameTree(p, q):
6  IF p = null AND q = null:  RETURN true
7  IF p = null OR q = null:  RETURN false
8  IF p.val != q.val:  RETURN false
9  RETURN isSameTree(p.left, q.left) AND isSameTree(p.right, q.right)

← / → step · space play · Home restart

Every step in words

Show all 12 steps

Try node 3 as a candidate: call isSameTree(3, subRoot).
Values differ here: 3 in root versus 4 in subRoot. isSameTree(3, 4) returns false right away.
isSameTree(3, subRoot) was false, so 3 isn't a match by itself. Recurse into 3's left child (4) next, then its right child if that also fails.
Try node 4 as a candidate: call isSameTree(4, subRoot).
Compare (4, 4): values match. That alone isn't proof — recurse into the left children first, then the right.
Compare (1, 1): values match. That alone isn't proof — recurse into the left children first, then the right.
Both sides under (1, 1) matched, so isSameTree(1, 1) returns true.
Compare (2, 2): values match. That alone isn't proof — recurse into the left children first, then the right.
Both sides under (2, 2) matched, so isSameTree(2, 2) returns true.
Both sides under (4, 4) matched, so isSameTree(4, 4) returns true.
isSameTree(4, subRoot) came back true — the subtree rooted at 4 matches subRoot exactly. isSubtree returns true immediately; 4's other descendants are never checked.
Answer: true. The subtree rooted at 4 matches subRoot node-for-node, and isSubtree found it on the very first left turn from the root — node 5 on the right was never even visited. Each node is tried as a candidate at most once, and each candidate costs at most O(m) to check, giving O(n * m) overall.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Subtree of Another Tree in the editor All Binary Trees problems Back to roadmap