LeetCode Solutions Blog

Subtree of Another Tree

Number: 572

Difficulty: Easy

Paid? No

Problem Description

Determine if one binary tree (subRoot) is exactly a subtree of another binary tree (root). A subtree is defined as a node in the main tree and all of its descendants.

Key Insights

Use Depth-First Search (DFS) to visit each node in the main tree.
At each node, check if the subtree starting from that node is identical to subRoot.
A helper function is used to compare the structure and node values of two trees.
Consider recursion as the primary approach to traverse and compare trees.
Early exit when a mismatch is found can optimize average-case performance.

Space and Time Complexity

Time Complexity: O(m * n) in the worst case, where m is the number of nodes in the main tree and n is the number of nodes in the subRoot tree.
Space Complexity: O(max(depth of main tree, depth of subRoot)) due to recursive call stack.

Solution

We solve the problem by performing a DFS traversal on the main tree. For each visited node, a helper function checks whether the subtree starting at that node is identical to subRoot by comparing node values and recursively checking both left and right subtrees. This method leverages recursion effectively and provides early termination if mismatches occur, allowing for efficient traversal and comparison.

Code Solutions

# Python solution for checking if subRoot is a subtree of root.

# 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: TreeNode, subRoot: TreeNode) -> bool:
        # Helper function to check if two trees are identical.
        def isSameTree(s, t):
            # Both nodes are None, trees match.
            if not s and not t:
                return True
            # One node is None or values differ.
            if not s or not t or s.val != t.val:
                return False
            # Recurse on left and right subtrees.
            return isSameTree(s.left, t.left) and isSameTree(s.right, t.right)
        
        # Base case: if root is None, then no subtree exists.
        if not root:
            return False
        # Check if current subtree is identical to subRoot.
        if isSameTree(root, subRoot):
            return True
        # Recursively check left and right subtrees.
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)