**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
```