# Serialize and Deserialize BST
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/serialize-and-deserialize-bst)
Canonical: https://scaleengineer.com/dsa/problems/serialize-and-deserialize-bst
**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)
**Data structures:** String, Tree, Binary Tree, Binary Search Tree
---
## Problem
Serialization is 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 search tree**. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

**The encoded string should be as compact as possible.**

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* The number of nodes in the tree is in the range `[0, 104]`.
* `0 <= Node.val <= 104`
* The input tree is **guaranteed** to be a binary search tree.

# Approaches
## Pre-order Traversal with Null Markers
This approach treats the Binary Search Tree as a general Binary Tree. It serializes the tree using a pre-order traversal, explicitly storing null children with a special marker (e.g., 'N' or '#'). This ensures that the structure can be perfectly reconstructed, but it doesn't take advantage of the BST properties, leading to a less compact string as requested by the problem.
**Time:** O(N), where N is the number of nodes in the tree. Both serialization and deserialization visit each node (and null marker position) exactly once. · **Space:** O(N), where N is the number of nodes. The space is dominated by the storage for the serialized string (which includes nodes and null markers) and the recursion stack. In the worst case of a skewed tree, the recursion depth can be O(N).
**Pros:** Simple to implement and understand.; Works for any binary tree, not just BSTs.
**Cons:** The serialized string is not compact because it stores redundant null markers.; Does not leverage the properties of a BST for optimization.
### Explanation
### Serialization
A recursive Depth-First Search (DFS) function, specifically pre-order, is used. The function traverses the tree in the order: `root -> left -> right`. When a non-null node is encountered, its value is appended to a string builder, followed by a delimiter. When a null pointer is encountered (an empty child), a special marker (e.g., "N") is appended. This process creates a string that uniquely represents the tree structure, including its empty branches.

### Deserialization
The serialized string is first split by the delimiter into a list of values. A queue is a natural choice to process these values in the order they were generated. A recursive helper function builds the tree. It dequeues the next value. If the value is the null marker, it returns `null`. Otherwise, it creates a new node with the parsed integer value. It then recursively calls itself to build the left subtree and then the right subtree, perfectly reconstructing the original tree.

```java
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "N";

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

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP);
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    // 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(SEP)));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals(NULL)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(nodes);
        node.right = deserializeHelper(nodes);
        return node;
    }
}
```
### Algorithm
*   **Serialization:**
    1.  Define a recursive function `serializeHelper(node, stringBuilder)`.
    2.  If `node` is `null`, append a null marker (e.g., "N") and a separator to the `stringBuilder` and return.
    3.  Otherwise, append the `node.val` and a separator.
    4.  Recursively call `serializeHelper` for the left child.
    5.  Recursively call `serializeHelper` for the right child.
*   **Deserialization:**
    1.  Split the input string by the separator into a queue of strings.
    2.  Define a recursive function `deserializeHelper(queue)`.
    3.  Dequeue a value from the queue.
    4.  If the value is the null marker, return `null`.
    5.  Otherwise, create a new `TreeNode` with the parsed value.
    6.  Set the node's left child by recursively calling `deserializeHelper(queue)`.
    7.  Set the node's right child by recursively calling `deserializeHelper(queue)`.
    8.  Return the created node.

## Optimal Pre-order Traversal without Null Markers
This is the most efficient approach, specifically designed for a Binary Search Tree. It serializes the tree using a pre-order traversal but omits null markers. The inherent properties of a BST—that all nodes in the left subtree are smaller than the root and all nodes in the right subtree are larger—are sufficient to reconstruct the exact tree structure from just the sequence of node values in pre-order. This leads to the most compact string representation.
**Time:** O(N), where N is the number of nodes. Serialization is a simple pre-order traversal. Deserialization also processes each value from the serialized string exactly once to construct a node. · **Space:** O(H), where H is the height of the tree. The space is dominated by the recursion stack depth. In a balanced BST, this is O(log N), and in the worst case (a skewed tree), it is O(N). The serialized string itself takes O(N) space.
**Pros:** Produces the most compact string representation as it omits nulls.; Highly efficient in both time and space.; Leverages the core properties of a BST.
**Cons:** The deserialization logic is more complex than the general binary tree approach.; This method is specific to BSTs and cannot be used for general binary trees.
### Explanation
### Serialization
A standard pre-order traversal (DFS) is performed. For each non-null node encountered, its value is appended to a string, followed by a delimiter. Null children are simply ignored, as their absence can be inferred during deserialization. The resulting string is a compact list of the tree's node values in pre-order.

### Deserialization
The key insight is that the pre-order sequence can be used to rebuild the tree by keeping track of the valid range `(lower_bound, upper_bound)` for each node. The string is split into a list of node values. A recursive helper function, say `build(list, lower, upper)`, is used. We also use a global index to iterate through the list of values. The function checks if the current value at the global index is within the `(lower, upper)` range. If it is, a new node is created with this value, and the global index is advanced. The left child is built by a recursive call with an updated range: `build(list, lower, node.val)`. The right child is built by a recursive call with the range: `build(list, node.val, upper)`. If the current value is outside the range, it means this position corresponds to a null child, so we return `null`.

```java
public class Codec {
    private int idx;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        // Remove the trailing comma
        if (sb.length() > 0) {
            sb.setLength(sb.length() - 1);
        }
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) return;
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        String[] nodesStr = data.split(",");
        int[] nodes = new int[nodesStr.length];
        for (int i = 0; i < nodesStr.length; i++) {
            nodes[i] = Integer.parseInt(nodesStr[i]);
        }
        this.idx = 0;
        return build(nodes, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode build(int[] nodes, int lower, int upper) {
        if (idx == nodes.length || nodes[idx] < lower || nodes[idx] > upper) {
            return null;
        }
        
        int val = nodes[idx++];
        TreeNode node = new TreeNode(val);
        
        node.left = build(nodes, lower, val);
        node.right = build(nodes, val, upper);
        
        return node;
    }
}
```
### Algorithm
*   **Serialization:**
    1.  Define a recursive function `serializeHelper(node, stringBuilder)`.
    2.  If `node` is `null`, return.
    3.  Append `node.val` and a separator to the `stringBuilder`.
    4.  Recursively call `serializeHelper` for the left child.
    5.  Recursively call `serializeHelper` for the right child.
*   **Deserialization:**
    1.  Split the input string into an array of integers.
    2.  Initialize a global index `idx` to 0.
    3.  Define a recursive function `build(nodes, lower_bound, upper_bound)`.
    4.  Inside `build`, check if `idx` is out of bounds or if `nodes[idx]` is outside the `(lower_bound, upper_bound)` range. If so, return `null`.
    5.  Create a new `TreeNode` with the value `nodes[idx]`. Increment `idx`.
    6.  Set the node's left child by recursively calling `build(nodes, lower_bound, node.val)`.
    7.  Set the node's right child by recursively calling `build(nodes, node.val, upper_bound)`.
    8.  Return the created node.
    9.  Start the process by calling `build(nodes, Integer.MIN_VALUE, Integer.MAX_VALUE)`.

# Solutions
### 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 int i ; private List < String > nums ; private final int inf = 1 << 30 ; // Encodes a tree to a single string. public String serialize ( TreeNode root ) { nums = new ArrayList <>(); dfs ( root ); return String . join ( " " , nums ); } // Decodes your encoded data to tree. public TreeNode deserialize ( String data ) { if ( data == null || "" . equals ( data )) { return null ; } i = 0 ; nums = Arrays . asList ( data . split ( " " )); return dfs (- inf , inf ); } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } nums . add ( String . valueOf ( root . val )); dfs ( root . left ); dfs ( root . right ); } private TreeNode dfs ( int mi , int mx ) { if ( i == nums . size ()) { return null ; } int x = Integer . parseInt ( nums . get ( i )); if ( x < mi || x > mx ) { return null ; } TreeNode root = new TreeNode ( x ); ++ i ; root . left = dfs ( mi , x ); root . right = dfs ( x , mx ); return root ; } } // Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // String tree = ser.serialize(root); // TreeNode ans = deser.deserialize(tree); // return ans;
```

### 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 data = "" ; function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return ; } data += to_string ( root -> val ) + " " ; dfs ( root -> left ); dfs ( root -> right ); }; dfs ( root ); data . pop_back (); return data ; } // Decodes your encoded data to tree. TreeNode * deserialize ( string data ) { if ( data . empty ()) { return nullptr ; } vector < int > nums = split ( data , ' ' ); int i = 0 ; function < TreeNode * ( int , int ) > dfs = [ & ]( int mi , int mx ) -> TreeNode * { if ( i == nums . size () || nums [ i ] < mi || nums [ i ] > mx ) { return nullptr ; } int x = nums [ i ++ ]; TreeNode * root = new TreeNode ( x ); root -> left = dfs ( mi , x ); root -> right = dfs ( x , mx ); return root ; }; return dfs ( INT_MIN , INT_MAX ); } vector < int > split ( const string & s , char delim ) { vector < int > tokens ; stringstream ss ( s ); string token ; while ( getline ( ss , token , delim )) { tokens . push_back ( stoi ( token )); } return tokens ; } }; // Your Codec object will be instantiated and called as such: // Codec* ser = new Codec(); // Codec* deser = new Codec(); // string tree = ser->serialize(root); // TreeNode* ans = deser->deserialize(tree); // return ans;
```

### Python

```python
# Your Codec object will be instantiated and called as such: # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # tree = ser.serialize(root) # ans = deser.deserialize(tree) # return ans class Codec : # Encodes a tree to a single string. def serialize ( self , root : TreeNode ) -> str : sb = [] self . serializeHelper ( root , sb ) return ',' . join ( sb ) def serializeHelper ( self , root : TreeNode , sb : List [ str ]): if not root : return sb . append ( str ( root . val )) self . serializeHelper ( root . left , sb ) self . serializeHelper ( root . right , sb ) # Decodes your encoded data to tree. def deserialize ( self , data : str ) -> TreeNode : if not data : return None q = deque ( data . split ( ',' )) return self . deserializeHelper ( q , float ( '-inf' ), float ( 'inf' )) def deserializeHelper ( self , q : deque , lower : int , upper : int ) -> TreeNode : if not q : return None s = q [ 0 ] val = int ( s ) # here is the key, not in sub-tree range then meaning stop if val < lower or val > upper : return None # leave i-node to other tree branches q . popleft () root = TreeNode ( val ) root . left = self . deserializeHelper ( q , lower , val ) root . right = self . deserializeHelper ( q , val , upper ) return root ################# class Codec : def serialize ( self , root : Optional [ TreeNode ]) -> str : """Encodes a tree to a single string.""" def dfs ( root : Optional [ TreeNode ]): if root is None : return nums . append ( root . val ) dfs ( root . left ) dfs ( root . right ) nums = [] dfs ( root ) return " " . join ( map ( str , nums )) def deserialize ( self , data : str ) -> Optional [ TreeNode ]: """Decodes your encoded data to tree.""" def dfs ( mi : int , mx : int ) -> Optional [ TreeNode ]: nonlocal i if i == len ( nums ) or not mi <= nums [ i ] <= mx : return None # leave i-node to other tree branches x = nums [ i ] root = TreeNode ( x ) i += 1 root . left = dfs ( mi , x ) root . right = dfs ( x , mx ) return root nums = list ( map ( int , data . split ())) i = 0 return dfs ( - inf , inf ) ################# # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec : def serialize ( self , root : TreeNode ) -> str : """Encodes a tree to a single string.""" def dfs ( root ): if root is None : return nonlocal t t . append ( str ( root . val )) t . append ( ',' ) dfs ( root . left ) dfs ( root . right ) if root is None : return '' t = [] dfs ( root ) return '' . join ( t [: - 1 ]) def deserialize ( self , data : str ) -> TreeNode : """Decodes your encoded data to tree.""" def build ( s , l , r ): if l > r : return None root = TreeNode ( int ( s [ l ])) idx = r + 1 for i in range ( l + 1 , r + 1 ): if int ( s [ i ]) > root . val : idx = i break root . left = build ( s , l + 1 , idx - 1 ) root . right = build ( s , idx , r ) return root if not data : return None s = data . split ( ',' ) return build ( s , 0 , len ( s ) - 1 ) # Your Codec object will be instantiated and called as such: # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # tree = ser.serialize(root) # ans = deser.deserialize(tree) # return ans ############ # 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 """ stack = [( 1 , root )] ans = [] while stack : pc , node = stack . pop () if not node : continue if pc == 0 : ans . append ( str ( node . val )) else : stack . append (( 1 , node . right )) stack . append (( 1 , node . left )) stack . append (( 0 , node )) return "," . join ( ans ) def deserialize ( self , data ): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data : return None vals = data . split ( "," ) preOrder = map ( int , vals ) inOrder = sorted ( preOrder ) self . preIdx = 0 d = {} for i in range ( 0 , len ( inOrder )): d [ inOrder [ i ]] = i def helper ( preOrder , start , end , inOrder , d ): if start <= end : rootVal = preOrder [ self . preIdx ] self . preIdx += 1 root = TreeNode ( rootVal ) midPos = d [ rootVal ] root . left = helper ( preOrder , start , midPos - 1 , inOrder , d ) root . right = helper ( preOrder , midPos + 1 , end , inOrder , d ) return root return helper ( preOrder , 0 , len ( inOrder ) - 1 , inOrder , d ) # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.deserialize(codec.serialize(root))
```