Subtree of Another Tree

Subtree of Another Tree

This problem asks us to determine if a binary tree subRoot is a subtree of another binary tree root. This means there exists a node in root such that the tree rooted at that node is identical to subRoot.

Brute Force Approach

The brute force approach involves traversing the root tree and, for each node, checking if the subtree rooted at that node is identical to the subRoot tree. This involves a recursive comparison of the tree structures and node values.

Algorithm:

1. Traverse the root tree using a depth-first search (DFS).
2. At each node in root, call a helper function to check if the subtree rooted at that node is identical to subRoot.
3. The helper function recursively compares the structure and values of the current nodes in both trees. If a mismatch is found, return false. If both trees are exhausted simultaneously, return true.
4. If the helper function returns true for any node in root, then subRoot is a subtree of root. Otherwise, it is not.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSubtree(root: TreeNode, subRoot: TreeNode) -> bool:
    if not subRoot:
        return True
    if not root:
        return False

    def is_identical(node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2 or node1.val != node2.val:
            return False
        return is_identical(node1.left, node2.left) and is_identical(node1.right, node2.right)

    def traverse(node):
        if not node:
            return False
        if is_identical(node, subRoot):
            return True
        return traverse(node.left) or traverse(node.right)

    return traverse(root)

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, we might have to compare subRoot with every node in root.

Space Complexity: O(h), where h is the height of the root tree, due to the recursion stack during DFS.

Optimal Approach

The optimal approach still uses recursion, but combines the tree traversal and comparison logic to reduce the number of redundant comparisons.

Algorithm:

1. If subRoot is None, it's an empty tree and therefore a subtree of any tree. Return true.
2. If root is None but subRoot is not, then subRoot cannot be a subtree. Return false.
3. Check if the current root and subRoot are identical using a helper function (same as in the brute force approach).
4. If they are identical, return true.
5. If not, recursively check if subRoot is a subtree of either the left or right subtree of root.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSubtree(root: TreeNode, subRoot: TreeNode) -> bool:
    if not subRoot:
        return True
    if not root:
        return False

    def is_identical(node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2 or node1.val != node2.val:
            return False
        return is_identical(node1.left, node2.left) and is_identical(node1.right, node2.right)

    if is_identical(root, subRoot):
        return True
    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)

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, the algorithm might still need to explore all nodes in both trees.

Space Complexity: O(h), where h is the height of the root tree, due to the recursion stack during DFS.

Edge Cases:

• subRoot is None: An empty tree is considered a subtree of any tree, so return True.
• root is None: If subRoot is not also None, then subRoot cannot be a subtree, so return False.
• Both root and subRoot are None: Return True.
• One tree is much larger than the other. The algorithm should still function correctly, but the time complexity is affected by the size of the trees.
• Trees with identical values but different structures: The is_identical helper function handles structural differences.