# Python recursive solution with explanation

• ``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def check(s, t):
# helper function that does the actual subtree check
if (s is None) and (t is None):
return True
if (s is None) or (t is None):
return False
return (s.val == t.val and check(s.left, t.left) and check(s.right, t.right))

# need to do a pre-order traversal and do a check
# for every node we visit for the subtree
if not s:
# return False since None cannot contain a subtree
return
if check(s, t):
# we found a match
return True
if self.isSubtree(s.left, t) or self.isSubtree(s.right, t):
# a match was found
return True
return False

``````

• Hi! My solution is almost the same as yours but shorter with lesser checks for the helper function :)
I took this question's discussion as a reference:

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
# check if two trees are the same
def sametree(p, q):
if p and q:
return p.val == q.val and sametree(p.left, q.left) and sametree(p.right, q.right)
return p is q

if s is None:
return False
if sametree(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.