# 449. Serialize and Deserialize BST

Reference: LeetCode

Difficulty: Medium

## 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 search tree`

. There is no restriction on how your serialization/deserialization algorithm should work. You just 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.

**Note:** Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

## Analysis

Reference: Solution

To serialize a binary tree, we need to:

- Encode tree structure.
- Encode node values.
- Choose delimiters to separate the values in the encoded string.

### Preorder / Postorder Traversal

We can actually use the fact that BST could be constructed from `preorder`

or `postorder`

traversal only. It bases on the two facts:

- Binary tree could be constructed from
`preorder`

/`postorder`

and`inorder`

traversal. - Inorder traversal of BST is an array sorted in the ascending order:
`inorder = sorted(preorder)`

.

This means that BST structure (inorder) is already encoded in the preorder or postorder traversal.

**Time:** $O(N)$**Space:** $O(N)$

#### Postorder

1 | 6 |

Postorder: `[ 1 4 5 3 10 9 6 ]`

Read it from `right to left`

, the rightmost value would be the root’s value of a subtree.

**Serialize:**

1 | public String serialize(TreeNode root) { |

**Deserialize:**

1 | public TreeNode deserialize(String data) { |

#### Preorder

1 | 6 |

Postorder: `[ 6 3 1 5 4 9 10 ]`

Read it from `left to right`

, the leftmost value would be the root’s value of a subtree.

**Tiny Modification:**

1 | private void preorder(TreeNode root, StringBuilder sb) { |

### Other Optimizations

**Approach 1:** Convert int to 4-byte string to optimize space for node values.

**Approach 2:** Get rid of delimiters.

Since each integers could be represented as 4 bytes, we can treat the data as many chunks of 4 bytes.