# Subtree of Another [[tree|Tree]]
https://leetcode.com/problems/subtree-of-another-tree/
## Solution 1: [[dfs|DFS]] with [[recursion|Recursion]]
```python
def check(p, q):
return p.val == q.val if p and q else not p and not q
def sameTree(r1, r2):
queue = deque([(r1, r2)])
while queue:
p, q = queue.popleft()
if not check(p, q):
return False
if p:
queue.append((p.left, q.left))
queue.append((p.right, q.right))
return True
def isSubtree(root, subRoot):
if check(root, subRoot):
if sameTree(root, subRoot):
return True
return root.left and isSubtree(root.left, subRoot) \
or root.right and isSubtree(root.right, subRoot)
```
Time complexity: $O(MN)$, as for each of the $M$ nodes in `root`, we compare with $N$ nodes in the `subroot`.
## Solution 2: [[tree-serialize|Serialization]] with String Matching
Need a unique way to serialize the tree, also maintain the structure of subtrees (cannot use BFS). A single traversal is not sufficient. Two traversals (inorder + preorder or inorder + postorder) together can uniquely define a tree, but still cannot be used in the string matching.
```python
def serialize(node):
if node is None:
return '#'
tree_str += '^'
tree_str += str(node.val)
tree_str += serialize(node.left) + serialize(node.right)
return tree_str
return serialize(subroot) in serialize(root)
```