Subtree of Another Tree

Difficulty: Easy | Acceptance: 51.60% | Paid: No Topics: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot or false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

• Examples
• Constraints
• Approach 1: Depth-First Search (Recursive)
• Approach 2: Tree Serialization (String Matching)
• [Approach 3: Merkle Hashing]((#approach-3-merkle-hashing)

Examples

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

Constraints

The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

Approach 1: Depth-First Search (Recursive)

Intuition We traverse the main tree and for every node, we check if the subtree starting at that node is identical to the target subtree.

Steps

• Define a helper function isSameTree(s, t) that checks if two trees are identical.
• In the main function isSubtree, if the current node of root is null, return false.
• If isSameTree(root, subRoot) returns true, we found a match.
• Otherwise, recursively check the left subtree and the right subtree.

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot: return True
        if not root: return False
        if self.isSameTree(root, subRoot): return True
        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 or not q: return False
        if p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Complexity

• Time: O(M * N) in the worst case, where M and N are the number of nodes in root and subRoot.
• Space: O(max(M, N)) for the recursion stack.
• Notes: Simple to implement but can be slow for large trees.

Approach 2: Tree Serialization (String Matching)

Intuition Serialize both trees into strings (e.g., using pre-order traversal with markers for null nodes) and check if the serialized string of subRoot is a substring of the serialized string of root.

Steps

• Serialize root into a string s using a pre-order traversal, adding delimiters and null markers.
• Serialize subRoot into a string t using the same method.
• Check if t is a substring of s.

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)
        return serialize(subRoot) in serialize(root)

Complexity

• Time: O(M² + N²) for string concatenation in naive implementations, or O(M + N) with StringBuilder/KMP.
• Space: O(M + N) to store the serialized strings.
• Notes: Leverages standard string search algorithms but requires careful serialization to avoid collisions.

Approach 3: Merkle Hashing

Intuition Assign a unique hash to every node based on its value and the hashes of its children. If the hash of a node in root matches the hash of subRoot’s root, we verify the structure.

Steps

• Compute a hash for every node in subRoot and store the hash of the root.
• Compute a hash for every node in root.
• If a hash in root matches the target hash, perform a full tree comparison to confirm.

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        from hashlib import sha256
        
        def merkle(node):
            if not node:
                return "#"
            m = sha256()
            m.update(str(node.val).encode())
            m.update(merkle(node.left).encode())
            m.update(merkle(node.right).encode())
            return m.hexdigest()
        
        target = merkle(subRoot)
        
        def dfs(node):
            if not node: return False
            h = merkle(node)
            if h == target and self.isSameTree(node, subRoot):
                return True
            return dfs(node.left) or dfs(node.right)
        
        return dfs(root)
    
    def isSameTree(self, p, q):
        if not p and not q: return True
        if not p or not q: return False
        if p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Complexity

• Time: O(M + N) on average for hash computation, O(M * N) worst case if hash collisions occur frequently.
• Space: O(M + N) for recursion stack and hash storage.
• Notes: Efficient for very large trees where early pruning via hash is beneficial.