> For the complete documentation index, see [llms.txt](https://grind75-notes.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://grind75-notes.gitbook.io/notes/week-8/serialize-and-deserialize-binary-tree.md).

# Serialize and Deserialize Binary Tree

{% embed url="<https://leetcode.com/problems/serialize-and-deserialize-binary-tree>" %}

### Problem

> 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](https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation-). You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
>
> &#x20;
>
> **Example 1:**
>
> ![](https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg)
>
> <pre><code>Input: root = [1,2,3,null,null,4,5]
> <strong>Output: [1,2,3,null,null,4,5]
> </strong></code></pre>
>
> **Example 2:**
>
> <pre><code>Input: root = []
> <strong>Output: []
> </strong></code></pre>

### Pseudocode

```
- order of output is breath first
    - push nodes into queue and serialize values
    - remove any null values from the end of array
    - stringify array 

- parse input as into array
    - takes first three vals, as root, left, right
    - if values of left and right child exist
        - push them back into queue for their child nodes to be added if available
```

### Solution

```javascript
var serialize = function (root) {
  let output = [];
  let queue = root ? [root] : [];

  while (queue.length) {
    let node = queue.shift();

    if (node) {
      output.push(node.val);

      queue.push(node.left || null);
      queue.push(node.right || null);
    } else {
      output.push(null);
    }
  }

  while (output[output.length - 1] === null) {
    output.pop();
  }

  return JSON.stringify(output);
};

var deserialize = function (data) {
  const arr = JSON.parse(data);

  if (!arr.length) return null;

  const root = new TreeNode(arr.shift());
  const queue = [root];

  while (queue.length) {
    let node = queue.shift(),
      val;

    node.left = (val = arr.shift()) || val === 0 ? new TreeNode(val) : null;
    node.right = (val = arr.shift()) || val === 0 ? new TreeNode(val) : null;

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return root;
};
```

### Time and Space Complexity

#### Time

* What did the code do
* Total -

#### Space

* What did the code do
* Total -