Leetcode - 572. Subtree of Another Tree

Easy

Jan 12, 2026

#binary-tree

#dfs

572. Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

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

Example 2:

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

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].
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

Constraints:

Notes

Intuition

A subtree must match exactly starting from some node in the main tree. We need to check at every node whether the subtree rooted there is identical to subRoot.

Implementation

Create a helper function isSame that checks if two trees are identical (same structure and values). In the main function, if subRoot is null, it's trivially a subtree. If root is null but subRoot isn't, return false. Check if the current root matches subRoot using isSame. If not, recursively check if subRoot is a subtree of either the left or right child.

Edge-cases

A null subRoot is considered a subtree of any tree. Handle the case where root becomes null during recursion (subRoot can't exist in an empty tree).

Time: O(m * n) — where m and n are the sizes of the two trees
Space: O(n) — recursion stack

Complexity

Solution

from typing import Optional
from lcutils import TreeNode

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSame(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSame(p.left, q.left) and self.isSame(p.right, q.right)
        else:
            return False
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False
        if self.isSame(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()