Problem

Given two binary trees, root and subRoot, determine whether subRoot exists somewhere inside root.

A subtree is any node along with all of its descendants. The entire tree also counts as a subtree of itself.

For example:

root:
        1
      /   \
     2     3
    / \
   4   5

subRoot:
      2
     / \
    4   5

Output:

True

However, if even a single node differs, it is not considered the same subtree.

Intuition

This problem is really a combination of two problems:

  1. Traverse every node in the main tree.
  2. At each node, check whether the subtree rooted there is identical to subRoot.

Notice how similar the second step is to LeetCode 100. Same Tree.

LeetCode 100. Same Tree – Explanation
Given the roots of two binary trees p and q, determine whether they are exactly the same. Two binary trees are considered the same if: They have the same structure. Every corresponding node contains the same value
LeetCode 100. Same Tree – Explanationmore posts

The algorithm is therefore:

  • Visit a node in root.
  • Compare that entire subtree with subRoot.
  • If they are identical, return True.
  • Otherwise, recursively search the left subtree.
  • If still not found, recursively search the right subtree.

Eventually either:

  • we find a matching subtree, or
  • we visit every node and return False.

Solution

from typing import Optional

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:

        def sameTree(s, t):
            if not s and not t:
                return True

            if s and t and s.val == t.val:
                return (
                    sameTree(s.left, t.left) and
                    sameTree(s.right, t.right)
                )

            return False

        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)
        )

Step-by-Step

Suppose we have:

root

        3
      /   \
     4     5
    / \
   1   2

subRoot

      4
     / \
    1   2

Step 1

Start at the root (3).

sameTree(3, 4)

The values differ immediately.

False

Now recursively search both children.

Step 2

Move to node 4.

sameTree(4, 4)

Values match.

Now compare both left children.

1 == 1

Then both right children.

2 == 2

Every comparison succeeds.

True

The algorithm immediately returns True.

Why do we need sameTree()?

isSubtree() is responsible for finding candidate starting points.

sameTree() is responsible for verifying whether two trees are identical.

Keeping these responsibilities separate makes the code much cleaner.

Think of it like this:

isSubtree()
    ↓
Try every node in root

        ↓

sameTree()
    ↓
Are these two trees identical?

Base Cases

There are several important base cases.

1. Both nodes are None

if not s and not t:
    return True

Two empty trees are identical.

2. Values match

if s and t and s.val == t.val:

Only then do we recursively compare both left and right children.

3. Everything else

return False

This covers:

  • one node is None
  • values differ
  • structures differ

4. subRoot is empty

if not subRoot:
    return True

An empty tree is considered a subtree of every tree.

5. root becomes empty

if not root:
    return False

We've searched the entire tree without finding a match.

Time Complexity

Let:

  • n = number of nodes in root
  • m = number of nodes in subRoot

For every node in root, we may compare an entire subtree with subRoot.

Worst case:

O(n × m)

Example:

root:
1
 \
 1
  \
   1
    \
     1
      \
       ...

subRoot:
1
 \
 1

Every node becomes a possible starting point.

Space Complexity

The recursive calls come from two places:

  • traversing root
  • comparing trees inside sameTree()

At any moment, the deepest recursion is bounded by the height of the trees.

Therefore:

O(h)

where h is the maximum height of the recursion stack.

  • Balanced tree:
O(log n)
  • Skewed tree:
O(n)

Interview Discussion

A brute-force approach would compare subRoot against every node, which is exactly what this recursive solution does. Since each comparison uses the optimal Same Tree algorithm, this is the standard interview solution and is accepted by virtually every interviewer.

For larger trees (where n can be much bigger than 100), interviewers might ask whether you can improve the worst-case O(n × m) time complexity.

Common follow-up optimizations include:

  • Serializing both trees and using string matching (such as KMP).
  • Computing hashes for each subtree (Merkle hashing / rolling hashes).

These approaches can reduce the average runtime to approximately O(n + m), although they are considerably more complex and are usually discussed only as follow-up optimizations.

Key Takeaways

  • This problem is essentially Same Tree repeated at every node.
  • Traverse every node in root.
  • At each node, compare the subtree using the Same Tree algorithm.
  • Return immediately once a match is found.
  • Worst-case time complexity is O(n × m).
  • Space complexity is O(h), where h is the height of the recursion stack.