# 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/32442719377939-How-to-create-test-cases-on-LeetCode#h_01J5EGREAW3NAEJ14XC07GRW1A). You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg align="center")

```plaintext
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
```

**Example 2:**

```plaintext
Input: root = []
Output: []
```

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
    
*   `-1000 <= Node.val <= 1000`
    

## Solution

We use **level-order traversal** for both operations.

**Serialization:** Start with the root in a queue. Remove one item at a time and add its value to the string. For a real node, add its left and right children to the queue, even if they are `null`. Write `null` for each missing child. These markers preserve the tree’s shape: without them, we would know the node values but not where every child belongs.

**Deserialization:** Read the first value as the root and put it in a queue. Remove the next parent from the queue, then read the next two values as its left and right children. Create and queue each child whose value is not `null`. Repeat until all values have been read.

**Revision cue:** *Serialize: parent → left → right, including* `null`*. Deserialize: take a parent → read its next two children.*

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            if(node == null){
                sb.append("null ");
                continue;
            }

            sb.append(node.val);
            sb.append(" ");
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
        if(data == null || data == "") return null;

        String[] values = data.split(" ");

        if(values[0].equalsIgnoreCase("null")) return null;

        Queue<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.offer(root);

        for(int i=1; i<values.length; i++){
            
            TreeNode node = queue.poll();

            if(!values[i].equalsIgnoreCase("null")){
                node.left = new TreeNode(Integer.parseInt(values[i]));
                queue.offer(node.left);
            }

            i+=1;

            if(!values[i].equalsIgnoreCase("null")){
                node.right = new TreeNode(Integer.parseInt(values[i]));
                queue.offer(node.right);
            }
        }

        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
```