# Python solution with detailed explanation

• Subtree of Another Tree https://leetcode.com/problems/subtree-of-another-tree/#/description

Serialize and Search O(M+N)

• Serialize s and t using their preorder traversal.
• Be careful to include left and right child of leaves.
• Corner case: [12], [2]. This will resolve to "12,#,#" and "2,#,#". The latter is a substring of the former but [2] is not a subtree of [12].
• Disambiguate by serializing s and t as: "(12)(#)(#)" and "(2)(#)(#)".
• Then test whether serialization of t is a substring of s.
• Substring match using KMP is O(M+N). Space used is O(M+N).
``````class Solution(object):
def serialize(self, root, arr):
if root is None:
arr.append("#")
else:
arr.append("\(%s\)"%(root.val))
self.serialize(root.left, arr)
self.serialize(root.right, arr)
return

def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
s_ser, t_ser = [], []
self.serialize(s, s_ser)
self.serialize(t, t_ser)
return "".join(t_ser) in "".join(s_ser)
``````

Preorder Traversal O(MN)

• We need to test every node in s as a potential candidate for the root of a subtree which is the same as t.
• Traverse the tree in pre-order.
• For each node in the traversal, test if the node can be the root.
• Time complexity: O(MN). Space O(M+N)
``````class Solution(object):
def equals(self, s,t):
if s is None and t is None:
return True
elif s is not None and t is not None:
return (s.val == t.val) and self.equals(s.left, t.left) and self.equals(s.right, t.right)
else:
return False

def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
if self.equals(s,t):
return True
elif s is None:
return False
else:
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.