Problem Statement

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 and 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.

Link To the Problem

Intuition

A binary tree is composed of nodes, each having up to two children. To determine if one tree (subRoot) is a subtree of another (root), we need to check whether subRoot appears exactly somewhere inside root.

That means:

• There must exist a node in root such that the subtree rooted at that node is identical to subRoot.

• Two trees are identical if their node values and structure match perfectly.

Approach

We can solve this problem using a recursive approach:

1. Base idea:

• Traverse the main tree (root) node by node.

• At each node, check if the subtree starting there matches subRoot.

2. Helper function (compare)

• Compares two trees for equality.

• Returns True only if both are None or if their values and corresponding children are identical.

3. Recursive traversal (is_subtree)

• If the current subtree of root matches subRoot, return True.

• Otherwise, recursively check the left and right subtrees of root.

• If no match is found, return False.

This approach effectively checks all possible subtree roots in the main tree.

Complexity

• Time complexity: O(m * n), where m = number of nodes in root and n = number of nodes in subRoot. For each node in root , we may compare upto n nodes in subRoot.
• Space complexity: O(h) due to the recursion stack, where h is the height of the tree.

Code

# 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 compare(self,node1,node2) :
        if not node1 and not node2 :
            return True

        if not node1 or not node2 :
            return False

        if node1.val != node2.val :
            return False

        return self.compare(node1.left,node2.left) and self.compare(node1.right,node2.right)

    def is_subtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:

        if self.compare(root,subRoot) :
            return True

        if root.left and self.is_subtree(root.left,subRoot):
            return True

        if root.right and self.is_subtree(root.right,subRoot) :
            return True

        return False