Check if subtree

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def is_subtree(root1, root2):
    if root1 is None:
        return True
    if root2 is None:
        return False
    
    if is_identical(root1, root2):
        return True
    
    return is_subtree(root1, root2.left) or is_subtree(root1, root2.right)
 
# Function to check if two binary trees are identical or not
def is_identical(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
    
    return (root1.data == root2.data and
            is_identical(root1.left, root2.left) and
            is_identical(root1.right, root2.right))
 
# Example trees
# Tree 1
#         1
#       /   \
#      2     3
#     / \   / \
#    4   5 6   7
#             /
#            8
 
root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.left.right = Node(5)
root1.right.left = Node(6)
root1.right.right = Node(7)
root1.right.right.left = Node(8)
 
# Tree 2
#      3
#     / \
#    6    7
#   / \
#  8   9
 
root2 = Node(8)
# root2.left = Node(6)
# root2.right = Node(7)
# root2.left.left = Node(8)
# root2.left.right = Node(9)
 
# Test the function
if is_subtree(root2, root1):
    print("Tree 2 is a subtree of Tree 1")
else:
    print("Tree 2 is noot a subtree of Tree 1")