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:
Input: root = [2,1,3]
Output: [2,1,3]
Input: root = []
Output: []
Approach: We will store the preorder traversal here as inorder traversal is already known which is sorted order.
Implementation in C#:
public string serialize(TreeNode root)
{
if(root == null)
{
return string.Empty;
}
return string.Join('|', this.PreOrderSerialize(root));
}
public TreeNode deserialize(string data)
{
if (string.IsNullOrWhiteSpace(data))
{
return null;
}
List<string> nodeValues = data.Split("|").ToList();
TreeNode root = new TreeNode(int.Parse(nodeValues[0]));
this.MakeTree(nodeValues, root);
return root;
}
private void MakeTree(List<string> nodeValues, TreeNode root)
{
Stack<TreeNode> stackOfTreeVals = new Stack<TreeNode>();
stackOfTreeVals.Push(root);
for (int i = 1; i < nodeValues.Count; ++i)
{
TreeNode node = stackOfTreeVals.Peek();
int currVal = int.Parse(nodeValues[i]);
if (currVal < node.val)
{
node.left = new TreeNode(currVal);
stackOfTreeVals.Push(node.left);
}
else
{
while(stackOfTreeVals.Count > 0 && stackOfTreeVals.Peek().val < currVal)
{
node = stackOfTreeVals.Peek();
stackOfTreeVals.Pop();
}
node.right = new TreeNode(currVal);
stackOfTreeVals.Push(node.right);
}
}
}
private List<string> PreOrderSerialize(TreeNode node)
{
List<string> result = new List<string>();
if (node == null)
{
return result;
}
result.Add(node.val.ToString());
result.AddRange(this.PreOrderSerialize(node.left));
result.AddRange(this.PreOrderSerialize(node.right));
return result;
}
Complexity: O(n)
