The Insider's Guide to Serialize and Deserialize a Binary Tree using String

Problem Statement

This problem was asked by Google.

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.

For example, given the following Node class

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

C# Solution

We need to define a Serialization strategy using which we store the tree object in a string so that it can be later restored. Also, the structure of tree must be maintained.
Here, we use PreOrder Traversal with separator in the string to identify separation between nodes.
Also, for Deserialization we need to read the tree object back from the string which is achieved by reading each value from the separator and assigning it to in the PreOrder fashion.

Refer the code at http://rextester.com/KMIF68180

//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    // Definition for a binary tree node.
    public class Node<T> {
        public T val;
        public Node<T> left;
        public Node<T> right;
        public Node(T val): this(val, null, null){}
        public Node(T val, Node<T> left, Node<T> right) { 
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
 
    // Definition of Codec to serialize and deserialize nodes
    public class Codec<T> {
        string separator;
        public Codec(){
            separator = Guid.NewGuid().ToString();
        }
        
        // Encodes a tree to a single string using separator guid
        public string serialize(Node<T> root) {
            string retVal = separator;
            if(root == null){
                return retVal;
            }
            retVal += root.val;
            retVal += serialize(root.left);
            retVal += serialize(root.right);
            return retVal;
        }

        // Decodes your encoded data to tree using separator guid
        public Node<T> deserialize(string data) {
            var localData = data;
            return deserialize(ref localData);
        }
        
        // Decodes your encoded data to tree using separator guid and modifies the string in the operation
        public Node<T> deserialize(ref string data) {
            Node<T> root = null;
            
            // If reached the end of the string data
            if(data.IndexOf(separator, separator.Length) == -1){
                return root;
            }
            
            // Calculate Value
            var val = data.Substring(separator.Length, data.Substring(separator.Length).IndexOf(separator));
            
            // If no value present
            if(string.IsNullOrEmpty(val)){
                return root;                
            }
            
            // Evaluate Root
            root = new Node<T>(GetValue<T>(val));
            
            // Evaluate Left
            data = data.Substring(data.IndexOf(separator, separator.Length));
            root.left = deserialize(ref data);
            
            // Evaluate Right
            data = data.Substring(data.IndexOf(separator, separator.Length));
            root.right = deserialize(ref data);
            
            return root;
        }
        
        public static T GetValue<T>(String value)
        {
            return (T)Convert.ChangeType(value, typeof(T));
        }
    }
    
    public class Program
    {
        public static void Main(string[] args)
        {
            /*
            Given the root to a binary tree, implement serialize(root), which serializes the tree into a string,
            and deserialize(s), which deserializes the string back into the tree.
            
            node = Node('root', Node('left', Node('left.left')), Node('right'))
            assert deserialize(serialize(node)).left.left.val == 'left.left'
            */
            
            // Codec object will be instantiated and called as such:
            Codec<string> codec= new Codec<string>();
            
            Node<string> node = new Node<string>("root", 
                                                 new Node<string>("left", new Node<string>("left.left"), null), 
                                                 new Node<string>("right"));
            var serializedString = codec.serialize(node);
            var deserializedNode = codec.deserialize(serializedString);
            Console.WriteLine(deserializedNode.val);
            Console.WriteLine(deserializedNode.left.val);
            Console.WriteLine(deserializedNode.left.left.val);
            Console.WriteLine(deserializedNode.right.val);
            Console.WriteLine(node.right.val);
            Console.WriteLine(codec.deserialize(codec.serialize(node)).left.left.val == "left.left");
        }
    }
}