# Serialize and Deserialize Binary Tree

`Tree`, `Design`

**Hard**

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.

**Example:** 

```
You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as 
"[1,2,3,null,null,4,5]"
```

**Clarification:**The above format is the same as[how LeetCode serializes a binary tree](https://leetcode.com/faq/#binary-tree). You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

**Note:** Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

## Solution & Analysis

### Depth-first Search

**Pre-Oder Traversal**:

The preorder DFS traverse follows recursively the order of **root -> left subtree -> right subtree**.

```
[1,2,3,null,null,4,5]

---serialize--->

1,2,#,#,3,4,#,#,5,#,#,
```

用一个辅助的queue，存入data.split(",")之后的元素，这样在构建树时，就可以按照相同的顺序：**root -> left subtree -> right subtree**

**Complexity Analysis**

* Time complexity : in both serialization and deserialization functions, we visit each node exactly once, thus the time complexity is O(N), whereNNis the number of nodes, \_i.e.\_the size of tree.
* Space complexity : in both serialization and deserialization functions, we keep the entire tree, either at the beginning or at the end, therefore, the space complexity is O(N).

10 ms, faster than 92.02%

```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) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();

        traverse(root, sb);
        // System.out.println(sb.toString());

        return sb.toString();
    }

    private void traverse(TreeNode root, StringBuilder sb) {
        if (root != null) {
            sb.append(String.valueOf(root.val));
            sb.append(",");
            traverse(root.left, sb);
            traverse(root.right, sb);
        } else {
            sb.append("#");
            sb.append(",");
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        String[] values = data.split(",");

        Queue<String> queue = new LinkedList<String>(Arrays.asList(values));

        return buildTree(queue);
    }

    private TreeNode buildTree(Queue<String> queue) {
        if (queue == null || queue.isEmpty()) {
            return null;
        }
        String value = queue.poll();
        if (value.equals("#")) {
            return null;
        }

        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = buildTree(queue);
        node.right = buildTree(queue);
        return node;
    }
}

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

#### Concise Solution (serial part NOT RECOMMENDED)

via [@cdai](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74253/Easy-to-understand-Java-Solution/77363) -- 以下：代码比较简洁，但是serial的部分不是很readable的地方在于，何时加delimiter `","`

```
1,2,#,#,3,4,#,#,5,#,#
```

优点在保持了末尾不会有多余`","`, 但是逻辑上比较缠绕，一会pass by reference，一会返回值。因此尽管代码比较简洁，**不推荐在面试中使用**。

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

    public String serialize(TreeNode root) {
        return serial(new StringBuilder(), root).toString();
    }

    // Generate preorder string
    private StringBuilder serial(StringBuilder str, TreeNode root) {
        if (root == null) return str.append("#");
        str.append(root.val).append(",");
        serial(str, root.left).append(",");
        serial(str, root.right);
        return str;
    }

    public TreeNode deserialize(String data) {
        return deserial(new LinkedList<>(Arrays.asList(data.split(","))));
    }

    // Use queue to simplify position move
    private TreeNode deserial(Queue<String> q) {
        String val = q.poll();
        if ("#".equals(val)) return null;
        TreeNode root = new TreeNode(Integer.valueOf(val));
        root.left = deserial(q);
        root.right = deserial(q);
        return root;
    }
}
```

### Breadth-first Search - Queue

Serialize时类似 **pre-order traversal**. 这里为了节省空间，删去了末尾的"#"，虽然deserialized的时候并无影响。

Deserialize的时候要从左边节点开始填充，也就是说只有i % 2 == 1时才从queue中poll()，如果不为null，再生成新节点放入queue中。

```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) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        // sb.append('[');

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

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append('#');
            } else {
                sb.append(node.val);
                queue.offer(node.left);
                queue.offer(node.right);
            }
            sb.append(',');
        }

        // (optional, won't affect deserialization) remove tailing sharp and comma
        for (int i = sb.length() - 1; i >= 0; i--) {
            if (sb.charAt(i) == '#' || sb.charAt(i) == ',') {
                sb.deleteCharAt(i);
            } else {
                break;
            }
        }

        // sb.append(']');
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        String[] values = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);

        int i = 1;
        boolean isLeft = true;
        TreeNode node = null;
        while (i < values.length) {
            if (isLeft) {
                node = q.poll();
                if (values[i].equals("#")) {
                    node.left = null;
                } else {
                    node.left = new TreeNode(Integer.parseInt(values[i]));
                    q.offer(node.left);
                }
            } else {
                if (values[i].equals("#")) {
                    node.right = null;
                } else {
                    node.right = new TreeNode(Integer.parseInt(values[i]));
                    q.offer(node.right);
                }
            }
            isLeft = !isLeft;
            i++;
        }
        return root;
    }
}

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

## Reference

<https://leetcode.com/problems/serialize-and-deserialize-binary-tree/solution/>

<https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74253/Easy-to-understand-Java-Solution>

<https://www.jiuzhang.com/solutions/binary-tree-serialization/#tag-other>

<https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74260/Recursive-DFS-Iterative-DFS-and-BFS>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trees/serialize-and-deserialize-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.