LeetCode #572: Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/

To solve the LeetCode problem “Subtree of Another Tree”, we need to determine whether the given binary tree subRoot is a subtree of the binary tree root. Here are the steps to solve this problem using Python:

1. We start by defining a helper function validate(one, two) which will check if the two trees one and two are identical by checking if their values are equal and if their left and right subtrees are also identical. If either of the trees is None, we check if both trees are None.
2. Next, we define a recursive function helper(root) which will recursively traverse the root binary tree to check if the given subRoot is a subtree of the root. We do this by recursively checking if the current node in the root tree is identical to the given subRoot tree by calling the validate(one, two) function. If the current node is identical to the subRoot tree, we return True. If not, we recursively call the helper(root.left) and helper(root.right) functions until we reach the end of the root tree.
3. Finally, we call the helper(root) function from the main function isSubtree(root, subRoot) and return the result.

Here is the Python code to solve this problem:

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def helper(root):
            if not root:
                return False
            elif validate(root, subRoot):
                return True
            return helper(root.left) or helper(root.right)
        
        def validate(one, two):
            if not one or not two:
                return not one and not two
            return one.val == two.val and validate(one.left, two.left) and validate(one.right, two.right)
        
        return helper(root)

The time complexity of this solution is O(m * n) where m and n are the number of nodes in the root and subRoot trees respectively. This is because for each node in the root tree, we traverse the subRoot tree to check if it is identical to the current node in the root tree. The space complexity of this solution is O(max(m, n)) as it uses the call stack to store the recursive function calls.