Solution Explanation: Subtree of Another Tree

This problem asks whether one binary tree (subRoot) is a subtree of another binary tree (root). A subtree is a node in the larger tree and all of its descendants. The solution uses Depth-First Search (DFS).

Approach

The core idea is to recursively check if subRoot exists within root. This is done in two steps:

1. same(p, q) function: This helper function compares two trees (rooted at nodes p and q) for structural and value equality. It returns true if they are identical, and false otherwise. The base case is when either p or q is null; they are only equal if both are null. Otherwise, it recursively checks if the root values are equal and if their left and right subtrees are also equal.

2. isSubtree(root, subRoot) function: This function recursively searches for subRoot within root.

   • Base case: If root is null, it returns false (because a null tree cannot contain another tree).
   • It first checks if root and subRoot are the same using same(root, subRoot). If they are, it returns true.
   • Otherwise, it recursively calls isSubtree on the left and right subtrees of root, continuing the search. If either recursive call finds subRoot, it returns true. If neither finds it, it returns false.

Code Examples (Python)

# 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:
        def same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
            if p is None or q is None:
                return p is q  # Both None or both not None
            return p.val == q.val and same(p.left, q.left) and same(p.right, q.right)
 
        if root is None:
            return False
        return (
            same(root, subRoot)
            or self.isSubtree(root.left, subRoot)
            or self.isSubtree(root.right, subRoot)
        )
 

Time and Space Complexity Analysis

• Time Complexity: O(m * n), where 'n' is the number of nodes in root and 'm' is the number of nodes in subRoot. In the worst case, same function might be called for every node in root, and each call to same takes O(m) time to compare the structure of subRoot.

• Space Complexity: O(n) in the worst case, due to the recursive call stack depth which can be equal to the height of the root tree. The space used by the same function is O(m) but is reused in each recursive call.

The other language examples follow the same algorithmic approach, differing only in syntax. The time and space complexity remain consistent across all implementations.