Subtree of Another Tree

This problem requires us to determine if a binary tree subRoot is a subtree of another binary tree root. A subtree consists of a node in root and all of its descendants.

Naive Approach (Brute Force)

The most straightforward approach is to traverse the tree root and, for each node, check if the subtree rooted at that node is identical to subRoot. This involves a recursive comparison.

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 nodes in the two trees.
4. If a match is found, return true. Otherwise, continue traversing root.
5. If the traversal of root completes without finding a match, return false.

Code (Python)

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:
        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(N * M), 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. This is due to the recursive call stack during DFS.

Optimal Approach

An optimized approach involves converting the trees into strings and then using string matching. The key idea is that if subRoot is a subtree of root, then the string representation of subRoot should be a substring of the string representation of root. To ensure uniqueness, we need to include null markers in the string representation.

1. Define a function to serialize a tree into a string using a pre-order traversal, including null markers (e.g., "#") to represent empty nodes. A delimiter (e.g. comma) should also be used to seperate the nodes.
2. Serialize both root and subRoot into strings.
3. Check if the serialized string of subRoot is a substring of the serialized string of root.

Code (Python)

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node):
            if not node:
                return "#,"
            return str(node.val) + "," + serialize(node.left) + serialize(node.right)

        root_string = serialize(root)
        subroot_string = serialize(subRoot)

        return subroot_string in root_string

Time Complexity

• O(N + M), where N is the number of nodes in root and M is the number of nodes in subRoot. This is because we traverse both trees once to serialize them, and the substring check takes O(N) time in the worst case if using KMP algorithm.

Space Complexity

• O(N + M), to store the string representations of root and subRoot.

Edge Cases

• If subRoot is None, it's always a subtree (return True).
• If root is None, and subRoot is not, subRoot cannot be a subtree (return False).
• Trees with a single node.
• Large trees with deeply nested structures.

By using the string serialization approach, we avoid repeated comparisons of subtrees, leading to a more efficient solution.