Leetcode 572 - Subtree of Another Tree

Problem

Leetcode 572 - Subtree of Another Tree

Example:

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

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

Approach

We can solve this problem by checking whether the tree is the same as the subtree. We can use the same approach as in Leetcode 100.

Base case:

• If subRoot is None, return True
• If root is None, return False

Recursive case:

• Recursively call the function on the left and right subtrees of the current node

Visualization of the approach:

    3           4
   / \         / \
  4   5       1   2
 / \
1   2

3 == 4, False move on to the next node

4 == 4, True check the left and right subtrees
1 == 1, True
2 == 2, True

Since all the nodes are the same, return True.

Here is the implementation of the approach:

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # Base case (1): if subRoot is None, return True
        if not subRoot: return True

        # Base case (2): if root is None, return False
        if not root: return False

        # Base case (3): if the tree is the same as the subtree, return True
        if self.isSameTree(root, subRoot): return True

        # Recursive case: recursively call the function on the left and right subtrees of the current node
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q: return True
        if not (p and q and p.val == q.val): return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time Complexity and Space Complexity

The time complexity of this approach is $O(n \times m)$ since we are checking whether the tree is the same as the subtree.

The space complexity is $O(n)$ since we are using a recursive function.