572 Subtree of Another Tree

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

 

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^{4}\) <= root.val <= \(10^{4}\)
• \(-10^{4}\) <= subRoot.val <= \(10^{4}\)

 

2. Algorithms

We can check if there is a subtree of root with the same structure and node values of subRoot, by checking every subtrees while traverse the root tree. By checking cumulatively, we just check is there any True result that subtree is in root.

 

1. Start
2. (Base case1) If root is None, return False. (This means that we didn't find any subtree in root.)
3. (Base case2) If the result of isSame function is True, return True
   1. Declare function named isSame which got inputs as root and subRoot.
   2. If root is None and subRoot is None, return True. (There are no differences between two nodes.)
   3. If root is None or subRoot is None or values from two nodes are differnt, return False.
   4. Compare left subtrees and right subtrees separately and return result recursively.
4. Traverse left subtree and right subtree separately and connect them with 'or' logical operator.
5. Return result of logical operation
6. End

 

3. Codes

# 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: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if root is None : 
            return False
        if self.isSame(root, subRoot) : 
            return True 
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
        
    def isSame(self, root : Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool : 
        if root is None and subRoot is None : 
            return True 
        if root is None or subRoot is None or root.val != subRoot.val : 
            return False
        return self.isSame(root.left, subRoot.left) and self.isSame(root.right, subRoot.right)

 

4. Conclusion