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

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:

Deserialize:

Preorder

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:

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.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.