Pattern visualizer

Subtree of Another Tree

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. Animated on: Does root = [3,4,5,1,2] contain a subtree that matches subRoot = [4,1,2] exactly? Expected true..

Try every node in root as a candidate root

time O(n * m)space O(h)step 1 / 12

root | subRoot

Call stack

isSubtree(3)

line 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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap