EasyTreeDepth-First SearchString MatchingBinary TreeHash Function

Subtree of Another Tree

1 approach, code in every language

You are given the roots of two binary trees, root and subRoot. Determine whether subRoot appears as a subtree of root.

A subtree consists of some node in root together with all of that node's descendants; it matches subRoot when their structures and node values are identical. Return true if such a matching subtree exists, otherwise false.

Example 1

Input: root = [3,4,5,1,2], subRoot = [4,1,2]

Output: true

The node with value 4 and its two children exactly match subRoot.

Example 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]

Output: false

The candidate subtree rooted at 4 now has an extra child (0), so it no longer matches subRoot.

Constraints

The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4

Traverse Root, Compare Each Candidate

Visit every node of root and, at each one, run an exact same-tree comparison against subRoot.

Loading animation…

Intuition

A subtree match must start at some node of root, so we simply try every node as a potential anchor. At each anchor we run a helper sameTree that checks whether the two trees are structurally identical with equal values, walking both in lockstep. If any anchor produces a full match we are done; otherwise we recurse into the children of root and keep looking. This costs O(n * m) in the worst case because each of the n root nodes may trigger an O(m) comparison. A faster alternative serializes both trees into strings with explicit null markers and runs a substring search (for example KMP), giving O(n + m); the serialization must use delimiters so that values like 12 and 2 do not accidentally match.

Algorithm walkthrough

1If subRoot is null, treat it as a match and return true.
2If root is null while subRoot is not, return false.
3Run sameTree(root, subRoot): both null is a match, one null or unequal values is a mismatch.
4sameTree recurses on left-with-left and right-with-right children.
5If the current node matches, return true immediately.
6Otherwise recurse: return isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot).

Implementation

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def sameTree(a, b):
            if not a and not b:
                return True
            if not a or not b or a.val != b.val:
                return False
            return sameTree(a.left, b.left) and sameTree(a.right, b.right)

        if not subRoot:
            return True
        if not root:
            return False
        if sameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Time

O(n * m)

Space

O(n + m)

n and m are the node counts of root and subRoot; each anchor may trigger an O(m) comparison. The serialization + string-search alternative runs in O(n + m). Space is the combined recursion depth.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Does the Rig Hold This Section is our own problem on the technique behind Subtree of Another Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free