Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

```
I/P:
1
2 3
4 5
O/P: [1,2,3,null,null,4,5]
```

We need to traverse the tree in a traversal order and capture the nodes. We also need to make sure that the traversal order we pick helps us find the root from the serialized string. We can use preorder, which means the root will always be the first element in the serialized string.

Now, how to deserialize from the string?

For preorder, we know the traversal order is `root - left - right`

, so if we reverse-engineer, we know we will get the root first. The very next element would be its left child, the very next element would be its right child and so on. We can use that property to recursively re-construct the tree.

**Implementation: SerializeDeserialize**

`O(n)`

`O(n)`

For a skewed tree, our serialized string looks like `1,null,2,null,3,null,null`

. One quick optimization we can do is remove all the tail `null`

's. Why? Because if we reach the end of our LinkedList, we are going to return null's anyway.

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.

```
root:
3
4 5
1 2
subroot:
4
1 2
Output: true
root:
3
4 5
1 2
0
subroot:
4
1 2
Output: false
```

The subtree needs to start from *a* node in the tree. So first we need to find the node. Once we find the node, we need to make sure the tree is the same, including, the leaf nodes.

**Implementation: Subtree**

`O(n)`

The recursion stack, at most, will extend to all nodes of the tree. `O(n)`