Leetcode discuss: 428. Serialize and Deserialize N-ary Tree

June 22, 2022

Here is the link. 

C# | Quick learner | Add a test case | Ideas -> design -> C# code -> design

June 22, 2022
Introduction
I choose to work on hard level algorithm tagged Google. I like to continue to practice leetcode algorithms. How to be a good learner?

Good learner | What I did | Ideas -> design -> C# code -> design
I thought about the problem, how to serialize a n-ary tree, and then I read a few of discussion posts, and then I decided to study one of C# discuss post.

I could not fully understand the idea, so I added a test case, and then I can read the serialized string for given example in problem statement.

A n-ary tree

The above tree is serialized into the following string:
"1:3,3:2,5:0,6:0,2:0,4:0"
First visit nodes in the n-ary tree from root node, concatenate node's value with count of children node, and then take the approach of depth first approach.

For the above tree, 1:3,3:2, after the visit of node 1 followed by node 3, then it is time to visit 3's children nodes instead of root node 1's other children nodes.

With the detail of discussion of the above tree, the design is simple. We can argue that this design will keep all the information in order to deserialize and restore the n-ary tree.

Node constructor concern | Run-time exception

public Node(int _val) {
    val = _val;
}

I tried to use the above construct of Node to build node2, node4, node5, node6, and there is null pointer exception in the following code.

foreach(Node child in root.children) {
   serializeHelper(child, sb);
}

Top-voted discuss post
I took the approach by understanding working C# code, and then wrote a test case to debug the code, and understand serialized string first. Afterwards, it is time for me to go back to read more top-voted discuss posts, and then learn better about analysis.

The following C# code contains the solution code for the algorithm.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _428_serialize_n_ary_tree
{
    public class Node {
        public int val;
        public IList<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, IList<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public class Codec
    {
        static void Main(string[] args)
        {                      
            var node2 = new Node(2, new List<Node>());
            var node4 = new Node(4, new List<Node>());

            var node5 = new Node(5, new List<Node>());
            var node6 = new Node(6, new List<Node>());

            var node3Children = new List<Node>();

            node3Children.Add(node5);
            node3Children.Add(node6);

            var node3 = new Node(3, node3Children);
            var node1Children = new List<Node>();
            node1Children.Add(node3);
            node1Children.Add(node2);
            node1Children.Add(node4);

            var node1 = new Node(1, node1Children);

            // "1:3,3:2,5:0,6:0,2:0,4:0"
            var test = new Codec();
            var serialized = test.serialize(node1);
            Debug.Assert(serialized.CompareTo("1:3,3:2,5:0,6:0,2:0,4:0") == 0);

            var node = test.deserialize(serialized);
        }
        
        private const char BULKDELIMITER = ',';
        private const char NODEDELIMITER = ':';

        /// <summary>
        /// study code:
        /// https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/discuss/503844/C-clean-solution
        /// Serialize the tree given in the problem statement to a string:
        /// "1:3,3:2,5:0,6:0,2:0,4:0"
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public string serialize(Node root) {
            var sb = new StringBuilder();

            serializeHelper(root, sb);

            if (sb.Length > 0) {
                sb.Length--;
            }

            return sb.ToString();
        }
    
        private void serializeHelper(Node root, StringBuilder sb) {
            if (root == null) {
                return;
            }
        
            sb.Append(root.val.ToString());
            sb.Append(NODEDELIMITER);
            sb.Append(root.children.Count.ToString());
            sb.Append(BULKDELIMITER);

            //sb.Append($"{root.val}{NODEDELIMITER}{root.children.Count}{BULKDELIMITER}");
            foreach(Node child in root.children) {
                serializeHelper(child, sb);
            }
        }

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

            var strs = data.Split(new char[]{BULKDELIMITER});

            int p = 0;
            return deserializeHelper(strs, ref p);
        }
    
        /// <summary>
        /// 
        /// </summary>
        /// <param name="strs"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        private Node deserializeHelper(string[] strs, ref int p) {
            if (p == strs.Length) {
                return null;
            }
        
            var ss = strs[p].Split(new char[]{NODEDELIMITER});
            p++;

            int nodeVal = Int32.Parse(ss[0]);
            int childCount = Int32.Parse(ss[1]);

            var children = new List<Node>();

            for (int i = 0; i < childCount; i ++) {
                children.Add(deserializeHelper(strs, ref p));
            }

            return new Node(nodeVal, children);
        }
    }
}