Subtree of Another Tree

Check whether one full tree appears inside another tree.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Subtree of Another Tree: Search each main-tree node as a candidate root, then require equal values and equal left and right topology.

Input and goalCheck whether one full tree appears inside another tree.

Start at the main rootCall is_subtree(main3, sub4); same compares roots 3 and 4 before any child search.

nodevalueleft childright childmain33first-> main4-> main5main44-> main1-> main2main11-> null-> nullmain22-> null-> nullmain55-> null-> nullsub44second-> sub1-> sub2sub11-> null-> nullsub22-> null-> null

mainTreemain3(main4(main1,main2),main5)subTreesub4(sub1,sub2)callStackis_subtree(main3, sub4) -> same(main3, sub4)comparison3 != 4

Recognize it

Use this composition when one complete rooted tree must appear inside another: candidate roots may occur anywhere, but a candidate succeeds only if every value and missing-child position matches.

Keep true

is_subtree searches every reachable candidate root until one same call succeeds; same(first, second) returns true exactly when the two rooted trees have equal values and recursively identical left and right topology.

Reuse it

Separate locate from verify: DFS locates candidate roots, then a stricter recursive predicate proves complete structure; the same composition applies to tree patterns, AST fragments, and directory subtrees.

Pattern: DFS plus Same Tree.

Simple idea: At each node, check whether the trees are the same from that point. If not, search the left and right subtrees.

def is_subtree(root: TreeNode | None, subroot: TreeNode | None) -> bool:
   def same(first: TreeNode | None, second: TreeNode | None) -> bool:
      if first is None or second is None:
         return first is second
      return (
         first.val == second.val
         and same(first.left, second.left)
         and same(first.right, second.right)
      )

   if subroot is None:
      return True
   if root is None:
      return False
   return (
      same(root, subroot)
      or is_subtree(root.left, subroot)
      or is_subtree(root.right, subroot)
   )

Cost: $O(mn)$ time in the worst case and $O(h)$ call-stack space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.