public class Codec
{
    // Encodes a tree to a single string.
    public string serialize(TreeNode root)
    {
        if(root == null)
            return string.Empty;

        System.Text.StringBuilder output = new System.Text.StringBuilder();
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        output.Append(root.val);
        output.Append(','); // append ',' to separate node.values in the string

        while(q.Count > 0)
        {
            var node = q.Dequeue();

            if(node.left != null)
            {
                q.Enqueue(node.left);
                output.Append(node.left.val);
                output.Append(',');
            }
            else
            {
                output.Append('n');
                output.Append(',');
            }

            if(node.right != null)
            {
                q.Enqueue(node.right);
                output.Append(node.right.val);
                output.Append(',');
            }
            else
            {
                output.Append('n');
                output.Append(',');
            }
        }

        return output.ToString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        if(string.IsNullOrEmpty(data))
            return null;

        int nullValue = 1001; // Node.value <= 1000 so we can assign 1001 to null

        // Convert data into a list
        List<int> dataList = new List<int>();
        int i = 0;
        while(i < data.Length)
        {
            if(data[i] == 'n')
            {
                dataList.Add(nullValue);
                i+=2;
                continue;
            }

            int sign = 1;
            if(data[i] == '-')
            {
                sign = -1;
                i++;
            }
            int num = 0;
            while(data[i] != ',')
            {
                num = num * 10 + Convert.ToInt32(data[i].ToString());
                i++;
            }
            dataList.Add(sign * num);
            i++;
        }

        TreeNode root = new TreeNode(dataList[0]);
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);
        int index = 0;
        while(q.Count > 0)
        {

            var node = q.Dequeue();
            if(index + 2 < data.Length)
            {
                var left = dataList[index + 1];
                var right = dataList[index + 2];
                if(left != nullValue)
                {
                    TreeNode leftNode = new TreeNode(left);
                    node.left = leftNode;
                    q.Enqueue(node.left);
                }
                else
                {
                    TreeNode leftNode = null;
                    node.left = leftNode;
                }

                if(right != nullValue)
                {
                    TreeNode rightNode = new TreeNode(right);
                    node.right = rightNode;
                    q.Enqueue(node.right);
                }
                else
                {
                    TreeNode rightNode = null;
                    node.right = rightNode;
                }

                index = index + 2;
            }
        }

        return root;
    }
}