572: Subtree of Another Tree#

Difficulty: Easy

Link to Problem: To see the Subtree of Another Tree problem on LeetCode, click here!

Problem Description:

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

Constraints:

  1. The number of nodes in the root tree is in the range \([1, 2000]\).

  2. The number of nodes in the subRoot tree is in the range \([1, 1000]\).

  3. \(-10^4\) <= root.val <= \(10^4\)

  4. \(-10^4\) <= subRoot.val <= \(10^4\)

# 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, subRoot):
        if not root:
            return False
        
        # Check if the current subtree is equal to the subRoot
        if self.isSameTree(root, subRoot):
            return True
        
        # Recursively check the left and right subtrees
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
    
    def isSameTree(self, tree1, tree2):
        if not tree1 and not tree2:
            return True
        if not tree1 or not tree2:
            return False
        
        return (
            tree1.val == tree2.val and
            self.isSameTree(tree1.left, tree2.left) and
            self.isSameTree(tree1.right, tree2.right)
        )

This code defines a TreeNode class for the binary tree nodes and a Solution class with two methods:

  1. isSubtree: This method checks if there is a subtree of the root tree with the same structure and node values as the subRoot tree. It uses a helper function isSameTree to compare two trees for equality.

  2. isSameTree: This helper method recursively compares two trees to check if they are the same in structure and node values.

Here’s a detailed explanation of the code:#

  1. TreeNode Class:

The TreeNode class is defined to represent nodes in a binary tree. Each node has a val (the node’s value) and may have a left and right child.

  1. Solution Class:

    • The Solution class contains the solution for the problem and defines two important methods:

    • isSubtree(self, root, subRoot):

      • This method checks whether subRoot is a subtree of root. It takes two tree nodes, root and subRoot, as input arguments.

      • If root is None, it returns False because there is no subtree to search.

      • It then checks if the current subtree with root as its root is equal to subRoot using the isSameTree method. If they are the same, it returns True.

      • If the current subtree is not the same as subRoot, it recursively checks the left and right subtrees of root to see if subRoot is a subtree of any of them.

      • It returns True if subRoot is found in either the left or right subtree; otherwise, it returns False.

    • isSameTree(self, tree1, tree2):

      • This method checks whether two trees, tree1 and tree2, are the same.

      • If both tree1 and tree2 are None, they are considered the same tree, so it returns True.

      • If only one of them is None (but not both), they are different trees, so it returns False.

      • If both tree1 and tree2 have values, it checks if their values are equal and recursively checks if their left and right subtrees are the same.

      • It returns True if the trees are the same; otherwise, it returns False.

The code effectively uses recursion to traverse the binary trees and check for subtree equality. The isSubtree method starts the recursive search, and the isSameTree method is used to compare individual subtrees. The approach is efficient and avoids unnecessary checks when possible.

This solution allows you to determine if there exists a subtree within the root tree that matches the structure and node values of subRoot.

Test cases#

#root = [3,4,5,1,2]
#subRoot = [4,1,2]

# Example input
root = TreeNode(3)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(2)

subRoot = TreeNode(4)
subRoot.left = TreeNode(1)
subRoot.right = TreeNode(2)

# Create an instance of the Solution class
solution = Solution()

# Test the isSubtree method
result = solution.isSubtree(root, subRoot)
print("Is subRoot a subtree of root?", result)

Is subRoot a subtree of root? True

#root = [3,4,5,1,2,null,null,null,null,0] 
#subRoot = [4,1,2]


# Example input
root = TreeNode(3)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(0)

subRoot = TreeNode(4)
subRoot.left = TreeNode(1)
subRoot.right = TreeNode(2)

# Create an instance of the Solution class
solution = Solution()

# Test the isSubtree method
result = solution.isSubtree(root, subRoot)
print("Is subRoot a subtree of root?", result)

Is subRoot a subtree of root? False

Let’s analyze the time and space complexity of the provided code for the “Subtree of Another Tree” problem:

Time Complexity

The time complexity of the code primarily depends on the recursive traversal of the binary tree. In both the isSubtree and isSameTree functions, we visit each node in the binary trees once. Let’s break down the time complexity:

  1. The isSubtree function:

    • In the worst case, we need to visit every node in the root tree.

    • For each node in the root tree, we call the isSameTree function, which has its own traversal.

    • So, the total time complexity is \(O(n * m)\), where \(n\) is the number of nodes in the root tree, and \(m\) is the number of nodes in the subRoot tree.

  2. The isSameTree function:

    • In the worst case, we visit every node in both tree1 and tree2.

    • The number of recursive calls made is proportional to the number of nodes in the trees.

    • So, the time complexity of this function is \(O(max(n, m))\), where \(n\) and \(m\) are the numbers of nodes in tree1 and tree2, respectively.

Overall, the time complexity of the entire code is \(O(n * m)\), where \(n\) is the number of nodes in the root tree, and \(m\) is the number of nodes in the subRoot tree. In practice, it may be less than \(O(n * m)\) if a subtree mismatch is detected early during the traversal.

Space Complexity

The space complexity of the code is determined by the function call stack during recursion and the space used by the recursive functions. Let’s analyze the space complexity:

  1. The isSubtree function:

    • It uses the call stack for recursion.

    • The maximum depth of the recursion is equal to the height of the root tree, which can be \(O(n)\) in the worst case (unbalanced tree).

    • Additionally, the function doesn’t use any significant extra space other than the recursion stack.

  2. The isSameTree function:

    • It also uses the call stack for recursion.

    • The maximum depth of the recursion is equal to the height of the tree1 or tree2, whichever is greater.

    • So, the maximum space used for the call stack is \(O(max(n, m))\).

In summary, the space complexity of the code is \(O(max(n, m))\) due to the function call stack. It scales with the maximum height of the trees being compared.

Overall, the code is efficient and works well for trees with moderate sizes. However, it’s important to keep in mind that the worst-case time complexity is \(O(n * m)\), so for very large trees, the performance may degrade.