572. Subtree of Another Tree

[#binary-tree, #dfs]

## description

## 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:

plain text

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

Example 2:

plain text

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

python

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

--EOF--