Serialization and De-serialization of an BST

https://leetcode.com/problems/serialize-and-deserialize-bst/, I've solved a similar problem before for a generic tree, but couldn't quite remember the solution. This one here uses a DFS-recursion to serialize and use a non-recursive method using a stack for de-serialization. Here is the problem statement:

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.

Let's take a look at the serialization: we'll be going down the tree in an DFS and will be encoding the tree in the following format (context-free grammar):

EncodedTree = ""

EncodedTree = <node value> + EncodedTreeNotEmpty

EncodedTreeNotEmpty = <node value> + L + EncodedTreeNotEmpty

EncodedTreeNotEmpty = <node value> + R + EncodedTreeNotEmpty

EncodedTreeNotEmpty = *

Here is an example of a serialized tree:

"10L5L1*R8**R15L11*R20R100R142*****"

The de-serialization will use a stack to control the state of the nodes, but the logic will be the following:

• Handle the base case
• Whenever you see an "L", peek the stack, create the left node, push it back into the stack
• Whenever you see an "R", peek the stack, create the right node, push it back into the stack
• Whenever you see an "*", pop out of the stack

The key point is to "peek: the item in the stack in steps 2 and 3 rather than pop. You do that until you reach the end of the string. And that's it! Cheers, Marcelo.

using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Numerics;

using System.Text;

using System.Threading.Tasks;

using System.IO;

namespace LeetCode

{

    class Program

    {

        static void Main(string[] args)

        {

            TreeNode tree = new TreeNode(10);

            tree.left = new TreeNode(5);

            tree.right = new TreeNode(15);

            tree.left.left = new TreeNode(1);

            tree.left.right = new TreeNode(8);

            tree.right.left = new TreeNode(11);

            tree.right.right = new TreeNode(20);

            tree.right.right.right = new TreeNode(100);

            tree.right.right.right.right = new TreeNode(142);

            Codec codec = new Codec();

            string codedTree = codec.serialize(tree);

            Console.WriteLine(codedTree);

            TreeNode dTree = codec.deserialize(codedTree);

            PrintTree(dTree);

        }

        static void PrintTree(TreeNode tree)

        {

            if (tree == null) return;

            Console.WriteLine(tree.val);

            PrintTree(tree.left);

            PrintTree(tree.right);

        }

    }

    public class TreeNode

    {

        public int val;

        public TreeNode left;

        public TreeNode right;

        public TreeNode(int x) { val = x; }

    }

    public class Codec

    {

        // Encodes a tree to a single string.

        public string serialize(TreeNode root)

        {

            if (root == null) return "";

            string retVal = root.val.ToString();

            if (root.left != null) retVal += "L" + serialize(root.left);

            if(root.right != null) retVal += "R" + serialize(root.right);

            return retVal + "*";

        }

        // Decodes your encoded data to tree.

        public TreeNode deserialize(string data)

        {

            if (String.IsNullOrEmpty(data)) return null;

            Stack stack = new Stack();

            int index = 0;

            int val = GetTreeValue(data, ref index);

            TreeNode tree = new TreeNode(val);

            TreeNode retVal = tree;

            stack.Push(tree);

            while (index < data.Length)

            {

                if (index < data.Length && data[index] == 'L')

                {

                    TreeNode treeFromStack = (TreeNode)stack.Peek();

                    index++;

                    val = GetTreeValue(data, ref index);

                    treeFromStack.left = new TreeNode(val);

                    stack.Push(treeFromStack.left);

                }

                else if (index < data.Length && data[index] == 'R')

                {

                    TreeNode treeFromStack = (TreeNode)stack.Peek();

                    index++;

                    val = GetTreeValue(data, ref index);

                    treeFromStack.right = new TreeNode(val);

                    stack.Push(treeFromStack.right);

                }

                else

                {

                    if(stack.Count > 0) stack.Pop();

                    index++;

                }

            }

            return retVal;

        }

        private int GetTreeValue(string data, ref int index)

        {

            int val = 0;

            while (index < data.Length && data[index] >= '0' && data[index] <= '9')

            {

                val = 10 * val + (int)(data[index] - '0');

                index++;

            }

            return val;

        }

    }

}