Serialize and Deserialize Binary Tree

Problem: Design an algorithm to serialize and deserialize a binary tree. Basically we need to ensure that a binary tree can be serialized to a string and this string can be deserialized back to the original tree structure.

Approach: In general we have seen that we can make binary tree using inorder and one of preorder or postorder traversal. A single traversal is not enough to make a tree back so what we can do is we can store both traversals' output (inorder and preorder) in a string while serializing and while deserializing we can use both traversals' output to build the original tree back.

The above approach will surely work but in the end we are going to need 2*N space and we are storing two traversals' output. Let's try to do better. We can use PreOrder traversal with some marker for NULL nodes. Basically while doing preorder traversal if we find a node is null then we store a marker say '$' in the serialization output and while doing deserialization if we see a '$', we can return NULL immediately.  That's all!

Implementation in C#:

        // Serialization of binary tree

        public string Serialize()

        {

            if (this.Root == null)

            {

                return string.Empty;

            }

            List<string> result = this.Serialize(this.Root);

            return string.Join('|', result);

        }

        private List<string> Serialize(BinaryTreeNode node)

        {

            List<string> result = new List<string>();

            if (node == null)

            {

                result.Add("$");

            }

            else

            {

                result.Add(node.Value.ToString());

                result.AddRange(this.Serialize(node.LeftNode));

                result.AddRange(this.Serialize(node.RightNode));

            }

            return result;

        }

        

        // Deserialization of binary tree

        public void Deserialize(string data)

        {

            if (string.IsNullOrWhiteSpace(data))

            {

                this.Root = null;

                return;

            }

            int currIndex = 0;

            this.Root = this.Deserialize(data.Split('|'), ref currIndex);

        }

        private BinaryTreeNode Deserialize(string[] data, ref int currIndex)

        {

            if (data[currIndex] == "$")

            {

                return null;

            }

            BinaryTreeNode node = new BinaryTreeNode(int.Parse(data[currIndex]));

            ++currIndex;

            node.LeftNode = this.Deserialize(data, ref currIndex);

            ++currIndex;

            node.RightNode = this.Deserialize(data, ref currIndex);

            return node;

        }

Complexity: O(n) for both serialize and deserialize operations.