Q58: Subtree of Another Tree. - DSA Patterns (Multi-Lang)

In Simple Words: For every node in root, check if tree rooted here is identical to subRoot using isSameTree. If not, recursively test isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot).

Time: $O(N \cdot M)$ | Space: $O(H)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def isSubtree(root: TreeNode | None, subRoot: TreeNode | None) -> bool:
    if not subRoot: return True
    if not root: return False
    def isSame(t1, t2):
        if not t1 and not t2: return True
        if not t1 or not t2 or t1.val != t2.val: return False
        return isSame(t1.left, t2.left) and isSame(t1.right, t2.right)
    if isSame(root, subRoot): return True
    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)