# Serialize and Deserialize Binary Tree
**Difficulty:** HARD
[External](https://leetcode.com/problems/serialize-and-deserialize-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/serialize-and-deserialize-binary-tree
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
**Data structures:** String, Tree, Binary Tree
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nvidia](https://scaleengineer.com/companies/nvidia), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Citadel](https://scaleengineer.com/companies/citadel), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Workday](https://scaleengineer.com/companies/workday)
---
## 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%5F01J5EGREAW3NAEJ14XC07GRW1A). You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

**Example 1:**

![](https://assets.glich.co/dsa/serialize-and-deserialize-binary-tree/image0.jpg) 

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

**Example 2:**

**Input:** root = []
**Output:** []

**Constraints:**

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

# Approaches
## Level-Order Traversal (BFS)
This approach uses a Breadth-First Search (BFS), also known as a level-order traversal, to serialize the tree. We traverse the tree level by level, from left to right, and record the value of each node. A special marker (e.g., "N" or "#") is used for null nodes to ensure the tree's structure can be perfectly reconstructed.
**Time:** O(N) - Both serialization and deserialization processes visit each node exactly once, where N is the total number of nodes in the tree. · **Space:** O(N) - In the worst-case scenario (a complete binary tree), the maximum number of nodes in the queue at any time is proportional to the number of nodes in the tree (W ≈ N/2), leading to O(N) space. The string itself also takes O(N) space.
**Pros:** The logic is straightforward and follows the standard iterative BFS pattern.; It avoids deep recursion, which prevents potential `StackOverflowError` for very deep trees.
**Cons:** Can be less space-efficient than a DFS approach for balanced trees, as the queue's size is proportional to the tree's maximum width (O(N) in the worst case).; The serialized string might contain many trailing null markers for the last level, which can make the string longer than necessary (though this can be optimized).
### Explanation
### Serialization
The serialization process involves a level-order traversal using a queue. We start with the root. As we visit each node, we append its value to a string. If a node is `null`, we append a special marker. Crucially, for any non-null node we visit, we add both its left and right children to the queue, even if they are `null`. This ensures that the structure of the tree is preserved. The process continues until the queue is empty.

```java
public class Codec {
    private static final String NULL_SYMBOL = "N";
    private static final String DELIMITER = ",";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        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_SYMBOL).append(DELIMITER);
                continue;
            }
            sb.append(node.val).append(DELIMITER);
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return sb.toString();
    }
```

### Deserialization
To deserialize, we first split the string by our delimiter to get an array of values. The first value corresponds to the root. We create the root node and add it to a queue. This queue will keep track of the parent nodes whose children we need to attach. We then iterate through the rest of the values in pairs. For each parent node we dequeue, the next two values in the array represent its left and right children. If a value is not our null marker, we create a new node, attach it to the parent, and add the new node to the queue to have its own children attached later. This reconstructs the tree in the same level-order it was serialized.

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

        String[] nodes = data.split(DELIMITER);
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;

        while (!queue.isEmpty() && i < nodes.length) {
            TreeNode parent = queue.poll();

            // Left child
            if (!nodes[i].equals(NULL_SYMBOL)) {
                TreeNode left = new TreeNode(Integer.parseInt(nodes[i]));
                parent.left = left;
                queue.offer(left);
            }
            i++;

            // Right child
            if (i < nodes.length && !nodes[i].equals(NULL_SYMBOL)) {
                TreeNode right = new TreeNode(Integer.parseInt(nodes[i]));
                parent.right = right;
                queue.offer(right);
            }
            i++;
        }
        return root;
    }
}
```
### Algorithm
- **Serialization (BFS)**
  1. If the `root` is `null`, return an empty string or a specific marker for an empty tree.
  2. Initialize a queue (`java.util.Queue`) and add the `root` node to it.
  3. Initialize a `StringBuilder` to construct the serialized string.
  4. Loop while the queue is not empty:
     a. Dequeue a node `curr`.
     b. If `curr` is `null`, append a null marker (e.g., "N") and a delimiter to the `StringBuilder`.
     c. If `curr` is not `null`, append its value and a delimiter. Then, enqueue its left and right children.
  5. Return the final string from the `StringBuilder`.

- **Deserialization (BFS)**
  1. If the input string is empty or represents a null tree, return `null`.
  2. Split the input string by the delimiter to get an array of value strings.
  3. Create the `root` node from the first value in the array.
  4. Initialize a queue and add the `root` to it. This queue will hold parent nodes awaiting their children.
  5. Iterate through the rest of the value strings, starting from the second element (`i = 1`).
  6. In each iteration, dequeue a `parent` node.
  7. Process the next value string (`nodes[i]`) for the left child. If it's not the null marker, create a new node, attach it as `parent.left`, and enqueue the new node.
  8. Process the subsequent value string (`nodes[i+1]`) for the right child in the same manner.
  9. Continue until all values are processed and the tree is reconstructed.
  10. Return the `root`.

## Pre-order Traversal (DFS)
This approach utilizes a Depth-First Search (DFS), specifically a pre-order traversal (Root-Left-Right), for both serialization and deserialization. The pre-order sequence is ideal for reconstruction because the root of any subtree is always processed before its children, making it easy to rebuild the tree recursively.
**Time:** O(N) - Both serialization and deserialization require visiting each node and null marker once. Therefore, the time complexity is linear with respect to the number of nodes. · **Space:** O(N) - The space is dominated by the recursion call stack and the storage for the serialized string. The recursion depth is equal to the height of the tree, H. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N). The string itself also requires O(N) space.
**Pros:** Elegant and concise recursive implementation that naturally maps to the tree structure.; Generally more space-efficient for average and balanced trees, as the space complexity of the call stack is O(H), where H is the tree height (O(log N) for a balanced tree).
**Cons:** For very deep and skewed trees, the recursion depth can be large, potentially leading to a `StackOverflowError`.; The recursive implementation might be slightly less intuitive for beginners compared to the iterative BFS approach.
### Explanation
### Serialization
Serialization is performed using a recursive pre-order traversal. The helper function traverses the tree and builds a string. When it encounters a non-null node, it appends the node's value followed by a delimiter. When it encounters a `null` child pointer, it appends a special null marker (e.g., "#") and a delimiter. This marking of nulls is essential to distinguish between different tree structures that might otherwise have the same pre-order traversal of values.

```java
public class Codec {
    private static final String NULL_SYMBOL = "#";
    private static final String DELIMITER = ",";

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

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL_SYMBOL).append(DELIMITER);
        } else {
            sb.append(node.val).append(DELIMITER);
            buildString(node.left, sb);
            buildString(node.right, sb);
        }
    }
```

### Deserialization
For deserialization, we first split the string into a list or queue of values. We then use a recursive helper function that consumes values from this queue to build the tree. The function reads the next value: if it's the null marker, it returns `null`. Otherwise, it creates a new node with the value. Then, it makes a recursive call to build the left subtree and another to build the right subtree. Because the data is in pre-order, the recursive calls naturally consume the correct values from the queue to form the left and right subtrees in the correct order.

```java
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(DELIMITER)));
        return buildTree(nodes);
    }

    private TreeNode buildTree(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals(NULL_SYMBOL)) {
            return null;
        } else {
            TreeNode node = new TreeNode(Integer.parseInt(val));
            node.left = buildTree(nodes);
            node.right = buildTree(nodes);
            return node;
        }
    }
}
```
### Algorithm
- **Serialization (Pre-order DFS)**
  1. Define a recursive helper function, `buildString(node, stringBuilder)`.
  2. **Base Case**: If the current `node` is `null`, append a null marker (e.g., "#") and a delimiter to the `stringBuilder`, then return.
  3. **Recursive Step**: 
     a. Append the current `node.val` and a delimiter.
     b. Recursively call `buildString` for the left child: `buildString(node.left, stringBuilder)`.
     c. Recursively call `buildString` for the right child: `buildString(node.right, stringBuilder)`.
  4. The main `serialize` function initializes the `StringBuilder` and starts the recursion from the `root`.

- **Deserialization (Pre-order DFS)**
  1. Split the serialized string by the delimiter into a queue of values.
  2. Define a recursive helper function, `buildTree(nodesQueue)`.
  3. **Base Case**: Dequeue a value. If it's the null marker, return `null`.
  4. **Recursive Step**:
     a. Create a new `TreeNode` with the dequeued value.
     b. Reconstruct the left subtree by recursively calling `node.left = buildTree(nodesQueue)`.
     c. Reconstruct the right subtree by recursively calling `node.right = buildTree(nodesQueue)`.
     d. Return the created `node`.
  5. The main `deserialize` function initializes the queue and starts the recursion.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public string serialize ( TreeNode root ) { if ( root == null ) { return null ; } List < string > ans = new List < string >(); Queue < TreeNode > q = new Queue < TreeNode >(); q . Enqueue ( root ); while ( q . Count > 0 ) { TreeNode node = q . Dequeue (); if ( node != null ) { ans . Add ( node . val . ToString ()); q . Enqueue ( node . left ); q . Enqueue ( node . right ); } else { ans . Add ( "#" ); } } return string . Join ( "," , ans ); } // Decodes your encoded data to tree. public TreeNode deserialize ( string data ) { if ( data == null ) { return null ; } string [] vals = data . Split ( ',' ); int i = 0 ; TreeNode root = new TreeNode ( int . Parse ( vals [ i ++])); Queue < TreeNode > q = new Queue < TreeNode >(); q . Enqueue ( root ); while ( q . Count > 0 ) { TreeNode node = q . Dequeue (); if ( vals [ i ] != "#" ) { node . left = new TreeNode ( int . Parse ( vals [ i ])); q . Enqueue ( node . left ); } i ++; if ( vals [ i ] != "#" ) { node . right = new TreeNode ( int . Parse ( vals [ i ])); q . Enqueue ( node . right ); } i ++; } return root ; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { private static final String NULL = "#" ; private static final String SEP = "," ; // Encodes a tree to a single string. public String serialize ( TreeNode root ) { if ( root == null ) { return "" ; } StringBuilder sb = new StringBuilder (); preorder ( root , sb ); return sb . toString (); } private void preorder ( TreeNode root , StringBuilder sb ) { if ( root == null ) { sb . append ( NULL + SEP ); return ; } sb . append ( root . val + SEP ); preorder ( root . left , sb ); preorder ( root . right , sb ); } // Decodes your encoded data to tree. public TreeNode deserialize ( String data ) { if ( data == null || "" . equals ( data )) { return null ; } List < String > vals = new LinkedList <>(); for ( String x : data . split ( SEP )) { vals . add ( x ); } return deserialize ( vals ); } private TreeNode deserialize ( List < String > vals ) { String first = vals . remove ( 0 ); if ( NULL . equals ( first )) { return null ; } TreeNode root = new TreeNode ( Integer . parseInt ( first )); root . left = deserialize ( vals ); root . right = deserialize ( vals ); 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));
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * Encodes a tree to a single string. * * @param {TreeNode} root * @return {string} */ var serialize =
  function (root) {
    return rserialize(root, "");
  };
/** * Decodes your encoded data to tree. * * @param {string} data * @return {TreeNode} */ var deserialize =
  function (data) {
    const dataArray = data.split(" , ");
    return rdeserialize(dataArray);
  };
const rserialize = (root, str) => {
  if (root === null) {
    str += " #, ";
  } else {
    str += root.val + "" + " , ";
    str = rserialize(root.left, str);
    str = rserialize(root.right, str);
  }
  return str;
};
const rdeserialize = (dataList) => {
  if (dataList[0] === " # ") {
    dataList.shift();
    return null;
  }
  const root = new TreeNode(parseInt(dataList[0]));
  dataList.shift();
  root.left = rdeserialize(dataList);
  root.right = rdeserialize(dataList);
  return root;
}; /** * Your functions will be called as such: * deserialize(serialize(root)); */

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: // Encodes a tree to a single string. string serialize ( TreeNode * root ) { if ( ! root ) return "" ; string s = "" ; preorder ( root , s ); return s ; } void preorder ( TreeNode * root , string & s ) { if ( ! root ) s += "# " ; else { s += to_string ( root -> val ) + " " ; preorder ( root -> left , s ); preorder ( root -> right , s ); } } // Decodes your encoded data to tree. TreeNode * deserialize ( string data ) { if ( data == "" ) return nullptr ; stringstream ss ( data ); return deserialize ( ss ); } TreeNode * deserialize ( stringstream & ss ) { string first ; ss >> first ; if ( first == "#" ) return nullptr ; TreeNode * root = new TreeNode ( stoi ( first )); root -> left = deserialize ( ss ); root -> right = deserialize ( ss ); return root ; } }; // Your Codec object will be instantiated and called as such: // Codec ser, deser; // TreeNode* ans = deser.deserialize(ser.serialize(root));
```

### Python

```python
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec : def serialize ( self , root ): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if root is None : return '' res = [] def preorder ( root ): if root is None : res . append ( "#," ) return res . append ( str ( root . val ) + "," ) preorder ( root . left ) preorder ( root . right ) preorder ( root ) return '' . join ( res ) def deserialize ( self , data ): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data : return None vals = data . split ( ',' ) def inner (): first = vals . pop ( 0 ) if first == '#' : return None return TreeNode ( int ( first ), inner (), inner ()) # seems using a constructor __init__(val, left, right) return inner () # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # ans = deser.deserialize(ser.serialize(root)) ############ from collections import deque # bfs, each level based class Codec : def serialize ( self , root ): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ ret = [] queue = deque ([ root ]) while queue : top = queue . popleft () if not top : ret . append ( "None" ) continue else : ret . append ( str ( top . val )) queue . append ( top . left ) queue . append ( top . right ) return "," . join ( ret ) def deserialize ( self , data ): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ data = data . split ( "," ) if data [ 0 ] == "None" : return None root = TreeNode ( int ( data [ 0 ])) queue = deque ([ root ]) i = 0 while queue and i < len ( data ): top = queue . popleft () i += 1 left = right = None if i < len ( data ) and data [ i ] != "None" : left = TreeNode ( int ( data [ i ])) queue . append ( left ) i += 1 if i < len ( data ) and data [ i ] != "None" : right = TreeNode ( int ( data [ i ])) queue . append ( right ) top . left = left top . right = right return root # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.deserialize(codec.serialize(root))
```