## Algorithm

Problem Name: 449. Serialize and Deserialize BST

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.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
public class Codec {

public String serialize(TreeNode root) {
if (root == null) {
return "#";
}
StringBuilder sb = new StringBuilder();
dfsSerialize(root, sb);
return sb.toString().trim();
}

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

public TreeNode deserialize(String data) {
Queue < String> queue = new LinkedList<>(Arrays.asList(data.split("\\s+")));
return dfsDeserialize(queue);
}

private TreeNode dfsDeserialize(Queue < String> queue) {
if (queue.isEmpty()) {
return null;
}
String removed = queue.remove();
if (removed.equals("#")) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(removed));
root.left = dfsDeserialize(queue);
root.right = dfsDeserialize(queue);
return root;
}
}
``````
Copy The Code &

Input

cmd
root = [2,1,3]

Output

cmd
[2,1,3]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const serialize = function(root) {
const sb = [];
buildString(root, sb);
sb.pop();
return sb.join("");
};
function buildString(node, sb) {
if (node == null) return;
sb.push(node.val);
sb.push(splitter);
buildString(node.left, sb);
buildString(node.right, sb);
}

const deserialize = function(data) {
if (data.length === 0) return null;
const pos = [0];
return buildTree(
data.split(splitter),
pos,
Number.MIN_SAFE_INTEGER,
Number.MAX_SAFE_INTEGER
);
};
function buildTree(nodes, pos, min, max) {
if (pos[0] === nodes.length) return null;
let val = +nodes[pos[0]];
if (val  <  min || val > max) return null;
const cur = new TreeNode(val);
pos[0] += 1;
cur.left = buildTree(nodes, pos, min, val);
cur.right = buildTree(nodes, pos, val, max);
return cur;
}
``````
Copy The Code &

Input

cmd
root = [2,1,3]

Output

cmd
[2,1,3]

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
sing System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCode
{
public class _0449_SerializeAndDeserializeBST
{
public string serialize(TreeNode root)
{
var sb = PostOrder(root, new StringBuilder());
if (sb.Length > 0)
sb.Remove(sb.Length - 1, 1);

return sb.ToString();
}

public TreeNode deserialize(string data)
{
if (string.IsNullOrEmpty(data)) return null;

var nums = data.Split().Select(n => int.Parse(n)).ToList();
return Helper(int.MinValue, int.MaxValue, nums);
}

private StringBuilder PostOrder(TreeNode root, StringBuilder sb)
{
if (root == null) return sb;
PostOrder(root.left, sb);
PostOrder(root.right, sb);
sb.Append(root.val);
sb.Append(" ");
return sb;
}

private TreeNode Helper(int lower, int upper, IList < int> nums)
{
if (nums.Count == 0) return null;
var value = nums.Last();
if (value  <  lower || value > upper) return null;

nums.RemoveAt(nums.Count - 1);
var root = new TreeNode(value);
root.right = Helper(value, upper, nums);
root.left = Helper(lower, value, nums);
return root;
}
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]