# Binary Tree Serialization

## Introduction

What is serialization?

"In the context of data storage, serialization is the process of translating data structures or object state into a format that can be stored (for example, in a file or memory buffer, or transmitted across a network connection link) and reconstructed later in the same or another computer environment."

For example, if we want to serialize an array (data structure) `[1, 2, 3]` we can just store as (string) `[1, 2, 3]`.\
If we want to serialize a linked list, `1 -> 2 -> 3`, then we can store as `1 -> 2 -> 3`.\
If we want to serialize a hashmap, then we can store as `{"key" : "value"}`. (doesn't this remind you of json?)

Some applications in practice are XML, JSON, Protocol Buffers, etc.

## Question ([LC.297](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/))

> Design an algorithm to serialize and deserialize a binary tree.

## Example

```
    1
   / \
  2   3
     / \
    4   5
Serialized: [1, 2, 3, null, null, 4, 5]
```

## Analysis

How do we do this for a binary tree? We need to store the nodes in a certain order. What order should we pick We want the ones that the root is easy to identify. Aka preorder and level order (root will be stored first).

## Approach 1: BFS (Level Order Traversal)

**Serialize**

* Step 1 Construct Queue
* Step 2 Convert the queue to string

```
func serialize(root)
   Step 1 Construct Queue:
   if (root == null) return ""
   ArrayList<TreeNode> queue
   TreeNode current

   queue.enqueue(root)

   // how to get at the right index?
   // so this won't work and queue will never be empty
   // No, No, No we want to store the entire tree from the beginning
   --- ignore ---
   while (!queue.isEmpty) 
       current = queue.get() 
       if (current == null) continue
       queue.enqueue(current.left)
       queue.enqueue(current.right)
   end while
   --- end ignore ---

   // making the move
   for i from 0 to queue.size() - 1
       current = queue.get(i)
       if (current == null) continue
       queue.enqueue(current.left)
       queue.enqueue(current.right)        
   end for

   --- optional ---
   // take out the leaves (nulls) at the lowest level to save space
   while (queue.get(queue.size() - 1) == null)
       queue.dequeue
   end while
   --- end optional ---

   Step 2 Build String :
   StringBuild result
   result.append(queue.get(0).val);
   for i from 1 to queue.size() - 1
       if (queue.get(i) == null)
           result.append("," + "null")
       else
           result.append("," + queue.get(0).val)
   end for

   return result.toString
end func
```

**Deserialize**

* BFS on the encoded string

```
func deserialize(str)
   if (str.equals("")) return null
   String[] nodeValues = str.split(", ")

   Queue<TreeNode> queue
   index = 0
   TreeNode root = new TreeNode(nodeValue[index++])
   queue.enqueue(root)

   while (index < nodeValues.length) // or !queue.isEmpty
       current = queue.dequeue

       if (nodeValues[index] == "null") {
           leftChild = null
       } else {
           leftChild = new TreeNode(nodeValues[index])
           queue.enqueue(leftChild)
       }
       index++
       current.left = leftChild

       if (nodeValues[index] == "null") {
           rightChild = null
       } else {
           rightChild = new TreeNode(nodeValues[index])
           queue.enqueu(rightChild)
       }
       index++
       current.right = rightChild
   end while

   return root
end func
```

Notes: The goal of this approach is to make the thinking process as straightforward as possible. To be more elegant, we can store `nulls[i] for all i` to count the number nulls so far at each nodeValue. Then the left child will be `values[2 * (i - nulls[i]) + 1]` and the right child will be `values[2 * (i - nulls[i]) + 2]`.

## Approach 1 Code

```java
public class Codec {
    /**
     * Encodes a tree to a single string
     * Encoding format is (root, root.leftChild, root.rightChild, 
     * leftChild.leftChild, leftChild.rightChild, ...)
     * @param root the root of a binary tree
     * @return the serialization of the given binary tree
     */
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        // Step 1 Construct Queue
        // arraylist cause we want to store the entire tree
        ArrayList<TreeNode> queue = new ArrayList<>();
        TreeNode current;
        queue.add(root);

        for (int i = 0; i < queue.size(); i++) {
            current = queue.get(i);
            if (current != null) {
                queue.add(current.left);
                queue.add(current.right);
            }
        }

        // Step 2 Build String
        StringBuilder result = new StringBuilder();
        result.append(queue.get(0).val);
        for (int i = 1; i < queue.size(); i++) {
            result.append(", ");
            if (queue.get(i) == null) {
                result.append("null");
            } else {
                result.append(queue.get(i).val);
            }
        }

        return result.toString();
    }

    /**
     * Decodes the encoded data to a binary tree
     * @param data the serialzed binary tree (an encoded string)
     * @return the root of the restored binary tree
     */
    public TreeNode deserialize(String data) {
        if (data.equals("")) {
            return null;
        }

        String[] values = data.split(", ");
        Queue<TreeNode> queue = new LinkedList<>();
        int index = 0;
        TreeNode root = new TreeNode(Integer.parseInt(values[index++]));
        TreeNode current, leftChild, rightChild;

        queue.offer(root);
        while (index < values.length) { // or while (!queue.isEmpty())
            current = queue.poll();

            if (values[index].equals("null")) {
                leftChild = null;
            } else {
                leftChild = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(leftChild);
            }
            index++;
            current.left = leftChild;

            if (values[index].equals("null")) {
                rightChild = null;
            } else {
                rightChild = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(rightChild);
            }
            index++;
            current.right = rightChild;
        }

        return root;
    }
}
```

## Approach 2: DFS (Pre-order Traversal)

**Serialize**

* Just a regular preorder traversal
* Use a notebook (called result) to travel around the tree

```
func serialize(root)
    StringBuilder result
    preorder(root, result)
    return result
end func

func preorder(root, result)
    if (root == null)
        result.append("N ")
    result.append(root.val)
    result.append(" ")
    preorder(root.left, result)
    preorder(root.right, result)
end func
```

**Deserialize**

* We want to build this tree top down
* Naturally, the recursive divide and conquer fits this role

```
func deserialize(encoded_data)
    if (encoded_data == "null") return null
    String[] values = encoded_data.split(" ")
    return preorderDC(values)
end func

int index = 0
func preorderDC(values)
    if (index >= values.length) return null
    if (values[index] == "null") return null
    TreeNode root = new TreeNode(values[index])
    // we don't want to backtrack here
    // we want a permanent change
    // root.left = preorderDC(values, index + 1)
    index++
    root.left = preorderDC(values)
    index++
    root.right = preorderDC(values)
    return root
end func
```

## Approach 2 Code

```java
public class Codec {

    public String serialize(TreeNode root) {
        StringBuilder result = new StringBuilder();
        preorder(root, result);
        return result.substring(0, result.length() - 1);
    }

    private void preorder(TreeNode root, StringBuilder result) {
        if (root == null) {
            result.append("null ");
        } else {
            result.append(root.val);
            result.append(" ");
            preorder(root.left, result);
            preorder(root.right, result);
        }
    }

    public TreeNode deserialize(String data) {
        if (data.equals("null")) {
            return null;
        }
        String[] values = data.split(" ");
        return preorderDC(values); 
    }

    private int index = 0;
    private TreeNode preorderDC(String[] values) {
        // base case
        if (index >= values.length) {
            return null;
        }

        if (values[index].equals("null")) {
            return null;
        }

        // divide and conquer
        TreeNode root = new TreeNode(Integer.parseInt(values[index]));
        index++;
        TreeNode leftSubtree = preorderDC(values);
        index++;
        TreeNode rightSubtree = preorderDC(values);

        // merge
        root.left = leftSubtree;
        root.right = rightSubtree;
        return root;
    }
}
```

## Reference

Wikipedia [Serialization](https://en.wikipedia.org/wiki/Serialization#cite_note-1)


---

# 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://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/bfs/binary-tree-serialization.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.