Subtree of Another Tree

PracticeNeetCode ↗LeetCode ↗

Given the roots of two binary trees root and subRoot, return true if there exists a subtree of root with exactly the same structure and node values as subRoot.

Example

Key Pointers

• Reuse the Same Tree check as a helper — subRoot is present if it matches the tree rooted at some node exactly.
• Test the current node first; if that fails, recurse into the left and right children and try matching from there instead.
• Every node in root gets tried as a potential match root, so this builds directly on top of isSameTree.

Step-by-Step Analysis

1. Base case: if root is None, return False.
2. If isSameTree(root, subRoot) is True, return True.
3. Otherwise return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot).

Complexity

Time: O(n · m) worst case — Space: O(h)

Code

def isSubtree(root: TreeNode | None, subRoot: TreeNode | None) -> bool:
    if not root:
        return False
    if isSameTree(root, subRoot):
        return True
    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)

def isSameTree(p: TreeNode | None, q: TreeNode | None) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Code Explanation

How the solution above works, piece by piece.

1. Reaching an empty node of root means no match was found on this path → False.
2. If the tree starting here is identical to subRoot (using isSameTree), done.
3. Otherwise try every node below: the left subtree or the right subtree.
4. isSameTree is the node-by-node comparison from the Same Tree problem.
5. Worst case O(m · n): a full comparison may start at each of the m nodes.

Visual Walkthrough

Running it on root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]:

Video Explanation

NeetCode — Subtree of Another Tree, LeetCode 572