LeetCode #572 Easy

Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a node in root whose subtree is structurally identical to subRoot, including matching values.

binary treedfsrecursion

Open on LeetCode ↗

02

Intuition

💡

The trap is checking only whether values match somewhere in the tree, or stopping the search the moment you find a node whose value equals subRoot's root value. A value match by itself proves nothing about structure -- the subtree rooted there could easily branch differently or have different values further down, and it's tempting to treat that first value hit as decisive when it's really just a candidate. You need a full structural equality check, the same one used for 'Same Tree', run at every node of root as a candidate root: values must match at every corresponding position and the shapes must line up exactly, with both trees running out of nodes at the same spots. Just as important, a candidate that fails deep down does not disqualify the real match sitting somewhere else in the tree -- keep walking every node of root and trying the full comparison fresh each time, short-circuiting only once a genuine full match is found.

03

Approach

1

Write isSameTree as a helper

Build a standalone structural-equality check: two null nodes are equal, one null and one non-null are not, two non-null nodes are equal only if their values match and both their left and right subtrees are recursively equal.

2

Try every node of root as a candidate

Walk root with a DFS. At each node, call isSameTree(node, subRoot). If it returns true, the whole answer is true and you can stop. If it returns false, that just rules out this one candidate -- move on to the node's children and keep trying.

3

Don't let a value match short-circuit the search

Never treat 'the values are equal' alone as a signal to stop; only a true result from the full structural comparison ends the search. A failed comparison at one node is simply discarded, and the walk continues into both children looking for a better candidate.

04

Solution & live demo

python

▶1class Solution:
▶2    def isSubtree(self, root, subRoot):
▶3        def isSameTree(a, b):
▶4            if not a and not b:
▶5                return True
▶6            if not a or not b:
▶7                return False
▶8            if a.val != b.val:
▶9                return False
▶10            return isSameTree(a.left, b.left) and isSameTree(a.right, b.right)
▶11        def walk(node):
▶12            if not node:
▶13                return False
▶14            if isSameTree(node, subRoot):
▶15                return True
▶16            return walk(node.left) or walk(node.right)
▶17        return walk(root)

05

Edge cases

subRoot is null

An empty tree is conventionally considered a subtree of anything (isSameTree against null succeeds trivially at any null candidate), though most test suites don't exercise this directly -- follow the same isSameTree logic regardless.

root is null but subRoot is not

No candidate nodes exist to try, so the walk finds nothing and returns false.

Values match at a node but the shapes diverge just below it

isSameTree catches this correctly since it compares structure, not just values -- a matching root value with mismatched children still returns false for that candidate.

subRoot equals a non-root subtree deep in root

The walk must continue past failed candidates near the top and keep checking every descendant node, since the true match may be far from the root.

06

Complexity

Time

O(m * n)

Space

O(m + n)

In the worst case isSameTree (O(n), size of subRoot) runs at every node of root (O(m) nodes); recursion depth adds O(h1 + h2) space.