Subtree Of Another Tree Leetcode Problem 572 [Python Solution]

Subtree Of Another Tree problem falls under the category of tree-related questions and is classified as an “Easy” problem on Leetcode.

It’s worth noting that this problem has been encountered in technical interviews by companies such as Amazon, making it a valuable addition to your problem-solving repertoire.

Problem Overview

The problem is as follows: given two binary trees, root and subRoot, you need to determine whether subRoot is a subtree of root.

A subtree of a binary tree is defined as a tree that consists of a node in the main tree (root) and all its descendants.

Additionally, the main tree root can be considered as a subtree of itself.

Let’s illustrate this with an example:

Example 1:

Input:

- root: [3,4,5,1,2]
- subRoot: [4,1,2]

Output: true

In this case, the subRoot tree is indeed a subtree of the root tree.

Example 2:

Input:
- root: [3,4,5,1,2,null,null,null,null,0]
- subRoot: [4,1,2]

Output: false

Here, the subRoot tree is not a subtree of the root tree.

Constraints:

Before we delve into the solution, let’s take a look at the constraints of this problem:

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].
The values of nodes in both trees are within the range of -104 to 104.

Understanding the Constraints

Understanding the constraints of a problem is crucial before diving into the solution.

In this problem, there are two main constraints that influence our approach:

Size of Trees: The input trees can be relatively large, with up to 2000 nodes in the root tree and 1000 nodes in the subRoot tree.

Therefore, our solution should be efficient to handle such cases without causing a timeout.

Node Values: The values of nodes in both trees are integers within the range of -104 to 104. This constraint ensures that the values are manageable, and we don’t need to worry about exceptionally large or small values.

Subtree of Another Tree LeetCode Problem Solution

Now, let’s address the problem by considering two approaches: a brute-force solution and a more efficient one.

1. Bruteforce Approach

The brute-force approach involves comparing every node in the root tree with the subRoot tree to check if they match.

To do this, we can define a helper function called sameTree that recursively checks whether two trees are identical.

Here’s a Python implementation:

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

def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
    if not t:
        return True
    if not s:
        return False

    if self.sameTree(s, t):
        return True
    return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

def sameTree(self, s, t):
    if not s and not t:
        return True
    if s and t and s.val == t.val:
        return self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)
    return False

In this solution, we recursively traverse both trees, comparing nodes to check if they are identical.

If we find an identical subtree, we return True.

If not, we continue the search in both the left and right subtrees of the root tree.

This brute-force approach will work and give us the correct results.

However, it has a time complexity of O(s * t), where s and t represent the sizes of the root and subRoot trees, respectively.

In the worst case, this can be quite inefficient, especially when dealing with large trees.

2. Efficient Approach

To optimize our solution, we’ll use a more efficient approach.

The key idea is to use recursion to check if t is a subtree of the left or right subtree of s.

This way, we avoid unnecessary comparisons when we know that t is not a subtree of the entire s tree.

Here’s the Python code for the efficient approach:

View on GitHub ➹

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

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

        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not t:
            return True
        if not s:
            return False

        if self.sameTree(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def sameTree(self, s, t):
        if not s and not t:
            return True
        if s and t and s.val == t.val:
            return self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)
        return False

In this approach, we start with the base cases:
– If t is empty (i.e., None), we return True since an empty tree is considered a subtree of any tree.
– If s is empty but t is not, we return False because an empty tree cannot contain a non-empty subtree.

Next, if the sameTree helper function (which checks if two trees are the same) returns True, we know that t is a subtree of s, and we return True.

If none of the above conditions are met, we recursively check if t is a subtree of the left subtree of s or the right subtree of s.

We use an “or” (|) operation to indicate that we’re interested in any of these conditions being true.

If either the left or right subtree contains t, we return True.

This efficient approach minimizes unnecessary comparisons, improving the time complexity.

The time complexity is O(s * t), which is the best we can achieve for this problem, given the need to compare every node in both trees.

Time and Space Complexity

Time Complexity

The time complexity of both the brute-force and efficient approaches is O(s * t), where s and t represent the sizes of the root and subRoot trees, respectively.

This time complexity arises from the need to compare every node in both trees.

In the worst case, when both trees are large, this can be computationally intensive.

However, this is the most optimal time complexity achievable for this problem.

Space Complexity

The space complexity for both approaches is O(max(s, t)), where s and t are the sizes of the root and subRoot trees, respectively.

This space is used for the recursive call stack.

In the worst case, the space complexity depends on the depth of the recursion, which is determined by the height of the taller tree.

Reasoning Behind Our Approach

In this blog post, we explored two approaches to solving the Subtree Of Another Tree problem on LeetCode.

We started with a brute-force solution that involved comparing every node in the root tree with the subRoot tree.

This approach, while correct, had a time complexity of O(s * t), which could be inefficient for large trees.

To optimize the solution, we introduced an efficient approach that used recursion to check if t is a subtree of the left or right subtree of s.

This approach minimized unnecessary comparisons and achieved a time complexity of O(s * t), which is the best possible for this problem.

In the end, the efficient approach provides a practical and efficient solution for determining whether one tree is a subtree of another, even when dealing with large trees.

Conclusion

In this blog post, we addressed the LeetCode problem Subtree Of Another Tree We provided a detailed explanation of the problem, discussed the constraints, and presented two solutions: a brute-force approach and a more efficient approach.

We also explored the time and space complexity of both solutions, highlighting the trade-offs between them.

While the brute-force approach is correct, it may not be efficient for large trees.

The efficient approach, on the other hand, minimizes unnecessary comparisons and achieves the best possible time complexity.

In coding interviews, it’s essential to consider both correctness and efficiency when solving problems.

This problem serves as a valuable example of how to optimize a solution to handle large inputs efficiently.

If you found this blog post helpful, please consider liking and subscribing for more content.