LeetCode 572: Subtree Of Another Tree — Step-by-Step Visual Trace

#leetcode #algorithms #python #datastructures

Medium — Binary Tree | Depth-First Search | Tree Traversal | Recursion

The Problem

Given the roots of two binary trees, determine if the second tree (subRoot) is a subtree of the first tree (root). A subtree must include all descendants of a node in the original tree.

Approach

The solution uses a recursive approach with two helper functions: first traverse each node in the main tree, then at each node check if the subtrees rooted at that node are identical using a tree comparison function. This combines tree traversal with tree equality checking.

Time: O(m * n) · Space: O(max(m, n))

Code

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s:
            return False
        if self.isSameTree(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def isSameTree(self, p, q):
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)