> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/401-500/serialize-and-deserialize-bst.md).

# 449. Serialize and Deserialize BST

### Description

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.**

### 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.

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/serialize-and-deserialize-bst/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-serialize-and-deserialize-binary-tree-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** root = \[2, 1, 3]

**Output:** \[2, 1, 3]
{% endtab %}

{% tab title="Example 2" %}
**Input:** root = \[]

**Output:** \[]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

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

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        StringBuilder sb = new StringBuilder();
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node != null) {
                sb.append(node.val).append(",");
                stack.push(node.right);
                stack.push(node.left);
            } else {
                sb.append("#,");
            }
        }
        return sb.substring(0, sb.length()-1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        
        return helper(data.split(","), new int[]{0});
    }
    
    private TreeNode helper(String[] values, int[] index) {
        if("#".equals(values[index[0]])) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(values[index[0]]));
        
        index[0] += 1;
        node.left = helper(values, index);
        
        index[0] += 1;
        node.right = helper(values, index);
        
        return node;
    }
}

// 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;
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */
 
 public class Codec {

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

        StringBuilder sb = new StringBuilder();
        serialize(root, sb);

        return sb.substring(0, sb.length()-1);
    }
    
    private void serialize(TreeNode node, StringBuilder sb) {
        if(node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serialize(node.left, sb);
        serialize(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        
        return helper(data.split(","), new int[]{0});
    }
    
    private TreeNode helper(String[] values, int[] index) {
        if("#".equals(values[index[0]])) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(values[index[0]]));
        
        index[0] += 1;
        node.left = helper(values, index);
        
        index[0] += 1;
        node.right = helper(values, index);
        
        return node;
    }
}

// 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;
```

{% endtab %}
{% endtabs %}

### **Follow up**

*