LC572. Subtree of Another Tree

Approach 1: DFS

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot: return True
        if not root: return False
 
        if root.val == subRoot.val:
            if self._isSubtree(root, subRoot):
                return True
            
        return self.isSubtree(root.left, subRoot) or \
               self.isSubtree(root.right, subRoot)
    
    def _isSubtree(self, node1, node2):
        if node1 is None and node2 is None:
            return True
        
        if node1 is None or node2 is None:
            return False
        
        if node1.val == node2.val:
            return self._isSubtree(node1.left, node2.left) and \
                   self._isSubtree(node1.right, node2.right)
        
        return False

Complexity

Time: $O(mn)$ — where $n$ is number of nodes in tree and $m$ is number of nodes in subtree
Space: $O(m+n)$

Notes

Approach 2: String Matching / Tree HashingTODO-LC

Complexity

Time:
Space:

Notes