Try it here
Leetcode 572 Python Solution

Subtree of Another Tree


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.


Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false



  • 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].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104


# 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 not subRoot:
            return True
        if not root:
            return False
        if self.isSametree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
    def isSametree(self, r, s):
        if not r and not s:
            return True
        if r and s and r.val == s.val:
            return self.isSametree(r.left, s.left) and self.isSametree(r.right, s.right)
        return False

Writer profile pic

Uk01 on Feb 03, 2022 at 12:02 am

If you like and would like to contribute, you can write your article here or mail your article to . See your article appearing on the main page and help others to learn.

Post Comment

Comments( 0)


Forgot Password

Please enter your email address below and we will send you information to change your password.