Added solution for Leet Code 428

anxious-coder-lhs · anxious-coder-lhs · commit 1427c76f290f · 2020-11-01T12:52:51.000+05:30
diff --git a/README.md b/README.md
@@ -57,7 +57,8 @@ Happy to accept any contributions to this in any langugage.
 ## Hard
 1. [Find Missing Positive](https://leetcode.com/problems/first-missing-positive/) | [Solution](./level_hard/LeetCode_41_Hard.ts)
 2. [Read N Characters Given Read 4 II - Call Multiple Times - LeetCode 158](https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/) | [Solution 1](./level_hard/LeetCode_158_Hard.java) | [Solution 2 Optimized](./level_hard/LeetCode_158_Hard_1.java)
-3. [Serialize Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) | [Solution](./level_hard/SerializeDeserializeBinaryTree.ts)
+3. [Leet Code 297 - Serialize Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) | [Solution](./level_hard/SerializeDeserializeBinaryTree.ts)
+4. [Leet Code 428 - Serialize Deserialize N-Ary Tree](https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/) | [Solution](./level_hard/SerializeDeserializeNAryTree.ts)
 
 ## Sorting
 1. Bubble Sort | [Solution](./sorting/Sort_Bubble.js)
diff --git a/level_hard/SerializeDeserializeNAryTree.ts b/level_hard/SerializeDeserializeNAryTree.ts
@@ -0,0 +1,68 @@
+/**
+ * Definition for node.
+ * class Node {
+ *     val: number
+ *     children: Node[]
+ *     constructor(val?: number) {
+ *         this.val = (val===undefined ? 0 : val)
+ *         this.children = []
+ *     }
+ * }
+ */
+
+ /**
+  * Problem: Leet Code 428
+  * Solution: Uses the depth 1st traversal to serialize and deserialize the N-Ary tree. The ser and deser process
+  * uses a special marker with null(empty string) to determine that the current branch has ended. This helps us
+  * determine, that we have to backtrack and start adding new elements to the parents childs and so on.
+  * 
+  * Time: O(n) since all the nodes needs to be traversed at least once. Spsace: O(n) since at least additional space
+  * of n items is required.
+  * 
+  */
+class Codec {
+    constructor() {
+      
+  }
+  
+  // Encodes a tree to a single string.
+  serialize(root: Node | null): string {
+      const serialized: string[] = []
+      this.serializeHelper(root, serialized);
+      
+      return serialized.join(";");
+  };
+
+  serializeHelper(root: Node | null, serialized: string[]) {
+      if (root === null) return
+      serialized.push(root.val.toString())
+      if (root.children.length === 0) {
+          // Found a leaf node, ending a terminating null;
+          serialized.push("")
+      } else {
+          root.children.forEach(child => this.serializeHelper(child, serialized));
+          serialized.push("")
+      }
+  }
+  
+  // Decodes your encoded data to tree.
+  deserialize(data: string): Node | null {
+      const elements = data.split(";")
+      return this.deserializeHelper(elements);
+  };
+
+  deserializeHelper(elements: string[]): Node | null {
+      const value = elements.shift();
+      if (value === undefined || value === "") return null;
+      const root = new Node(parseInt(value));
+      let child;
+      while ( (child = this.deserializeHelper(elements)) !== null) {
+          root.children.push(child)
+      }
+      return root;
+  }
+}
+
+// Your Codec object will be instantiated and called as such:
+// Codec codec = new Codec();
+// codec.deserialize(codec.serialize(root));
