[LeetCode] Serialize and Deserialize BST

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)