{"id":"2987ad4f-9bb9-4ec6-baa4-c314a9b17162","name":"Serialize And Deserialize N - Ary Tree","description":"1. Serialization is to store tree in a file so that it can be later restored.\r\n2. The structure of tree must be maintained. Deserialization is reading tree back from file.\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you. ","constraints":"0 &lt;= Number of Nodes &lt;= 10^5\r\n-1000 &lt;= value of Node data &lt;= 1000","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n#include <stack>\r\n#include <stringstream>\r\nusing namespace std;\r\n\r\nclass Node\r\n{\r\npublic:\r\n int val;\r\n vector<Node*> children;\r\n\r\n Node() {}\r\n\r\n Node(int _val)\r\n {\r\n val = _val;\r\n }\r\n\r\n Node(int _val, vector<Node*> _children)\r\n {\r\n val = _val;\r\n children = _children;\r\n }\r\n};\r\n\r\n// Encodes a tree to a single string.\r\nstring serialize(TreeNode* root)\r\n{\r\n}\r\n\r\n// Decodes your encoded data to tree.\r\nTreeNode* deserialize(string s)\r\n{\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(TreeNode* node)\r\n{\r\n if (node == nullptr)\r\n return;\r\n\r\n string str = node->val + \"->\";\r\n for (Node* child : node->children)\r\n {\r\n str += child->val;\r\n }\r\n\r\n for (Node* child : node->children)\r\n {\r\n display(child);\r\n }\r\n}\r\n\r\nTreeNode* createTree(vector<int>& arr)\r\n{\r\n stack<Node*> st;\r\n for (int i = 0; i < arr.size - 1; i++)\r\n {\r\n string s = arr[i];\r\n if (s == \"null\")\r\n {\r\n Node* node = st.top();\r\n st.pop();\r\n st.peek()->children.add(node);\r\n }\r\n else\r\n {\r\n Node* node = new Node(stoi(s));\r\n st.push(node);\r\n }\r\n }\r\n\r\n return st.size() != 0 ? st.top() : nullptr;\r\n}\r\n\r\nvoid solve()\r\n{\r\n string str;\r\n cin >> str;\r\n stringstream ss(str);\r\n string word;\r\n vector<string> arr;\r\n while (ss >> word)\r\n arr.push_back(word);\r\n\r\n Node* root = createTree(arr);\r\n string s = serialize(root);\r\n display(deserialize(s));\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n static class Node {\r\n public int val;\r\n public ArrayList<Node> children;\r\n\r\n public Node() {\r\n children = new ArrayList<Node>();\r\n }\r\n\r\n public Node(int _val) {\r\n val = _val;\r\n children = new ArrayList<Node>();\r\n }\r\n\r\n public Node(int _val, ArrayList<Node> _children) {\r\n val = _val;\r\n children = _children;\r\n }\r\n }\r\n\r\n // Encodes a tree to a single string.\r\n public static String serialize(Node root) {\r\n\r\n }\r\n\r\n // Decodes your encoded data to tree.\r\n public static Node deserialize(String str) {\r\n\r\n }\r\n\r\n // input_Section=================================================\r\n public static void display(Node node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append(node.val + \" -> \");\r\n for (Node child : node.children) {\r\n sb.append(child.val + \" \");\r\n }\r\n System.out.println(sb.toString());\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node createTree(String[] arr) {\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length - 1; i++) {\r\n String s = arr[i];\r\n if (s.equals(\"null\")) {\r\n Node node = st.pop();\r\n st.peek().children.add(node);\r\n } else {\r\n Node node = new Node(Integer.parseInt(s));\r\n st.push(node);\r\n }\r\n }\r\n\r\n return st.size() != 0 ? st.pop() : null;\r\n }\r\n\r\n public static void solve() {\r\n String str = scn.nextLine();\r\n String[] arr = str.split(\" \");\r\n\r\n Node root = createTree(arr);\r\n String s = serialize(root);\r\n display(deserialize(s));\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"1 3 5 null 6 null null 2 null 4 null null","sampleOutput":"1 -> 3 2 4 \r\n3 -> 5 6 \r\n5 -> \r\n6 -> \r\n2 -> \r\n4 -> \r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"0c0daf13-c06a-4f84-a818-516cce1183de","name":"Serialize And Deserialize N - Ary Tree","slug":"serialize-and-deserialize-n-ary-tree","type":1}],"next":{"id":"4d442c4e-50c1-4076-983c-119844c4040d","name":"Serialize And Deserialize N - Ary Tree","type":0,"slug":"serialize-and-deserialize-n-ary-tree"},"prev":{"id":"391337ec-064f-47d9-922d-4992bcffa7bd","name":"Serialize And Deserialize Binary Tree","type":0,"slug":"serialize-and-deserialize-binary-tree"}}}

Serialize And Deserialize N - Ary Tree

1. Serialization is to store tree in a file so that it can be later restored. 2. The structure of tree must be maintained. Deserialization is reading tree back from file.

{"id":"2987ad4f-9bb9-4ec6-baa4-c314a9b17162","name":"Serialize And Deserialize N - Ary Tree","description":"1. Serialization is to store tree in a file so that it can be later restored.\r\n2. The structure of tree must be maintained. Deserialization is reading tree back from file.\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you. ","constraints":"0 &lt;= Number of Nodes &lt;= 10^5\r\n-1000 &lt;= value of Node data &lt;= 1000","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n#include <stack>\r\n#include <stringstream>\r\nusing namespace std;\r\n\r\nclass Node\r\n{\r\npublic:\r\n int val;\r\n vector<Node*> children;\r\n\r\n Node() {}\r\n\r\n Node(int _val)\r\n {\r\n val = _val;\r\n }\r\n\r\n Node(int _val, vector<Node*> _children)\r\n {\r\n val = _val;\r\n children = _children;\r\n }\r\n};\r\n\r\n// Encodes a tree to a single string.\r\nstring serialize(TreeNode* root)\r\n{\r\n}\r\n\r\n// Decodes your encoded data to tree.\r\nTreeNode* deserialize(string s)\r\n{\r\n}\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(TreeNode* node)\r\n{\r\n if (node == nullptr)\r\n return;\r\n\r\n string str = node->val + \"->\";\r\n for (Node* child : node->children)\r\n {\r\n str += child->val;\r\n }\r\n\r\n for (Node* child : node->children)\r\n {\r\n display(child);\r\n }\r\n}\r\n\r\nTreeNode* createTree(vector<int>& arr)\r\n{\r\n stack<Node*> st;\r\n for (int i = 0; i < arr.size - 1; i++)\r\n {\r\n string s = arr[i];\r\n if (s == \"null\")\r\n {\r\n Node* node = st.top();\r\n st.pop();\r\n st.peek()->children.add(node);\r\n }\r\n else\r\n {\r\n Node* node = new Node(stoi(s));\r\n st.push(node);\r\n }\r\n }\r\n\r\n return st.size() != 0 ? st.top() : nullptr;\r\n}\r\n\r\nvoid solve()\r\n{\r\n string str;\r\n cin >> str;\r\n stringstream ss(str);\r\n string word;\r\n vector<string> arr;\r\n while (ss >> word)\r\n arr.push_back(word);\r\n\r\n Node* root = createTree(arr);\r\n string s = serialize(root);\r\n display(deserialize(s));\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n static class Node {\r\n public int val;\r\n public ArrayList<Node> children;\r\n\r\n public Node() {\r\n children = new ArrayList<Node>();\r\n }\r\n\r\n public Node(int _val) {\r\n val = _val;\r\n children = new ArrayList<Node>();\r\n }\r\n\r\n public Node(int _val, ArrayList<Node> _children) {\r\n val = _val;\r\n children = _children;\r\n }\r\n }\r\n\r\n // Encodes a tree to a single string.\r\n public static String serialize(Node root) {\r\n\r\n }\r\n\r\n // Decodes your encoded data to tree.\r\n public static Node deserialize(String str) {\r\n\r\n }\r\n\r\n // input_Section=================================================\r\n public static void display(Node node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append(node.val + \" -> \");\r\n for (Node child : node.children) {\r\n sb.append(child.val + \" \");\r\n }\r\n System.out.println(sb.toString());\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node createTree(String[] arr) {\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length - 1; i++) {\r\n String s = arr[i];\r\n if (s.equals(\"null\")) {\r\n Node node = st.pop();\r\n st.peek().children.add(node);\r\n } else {\r\n Node node = new Node(Integer.parseInt(s));\r\n st.push(node);\r\n }\r\n }\r\n\r\n return st.size() != 0 ? st.pop() : null;\r\n }\r\n\r\n public static void solve() {\r\n String str = scn.nextLine();\r\n String[] arr = str.split(\" \");\r\n\r\n Node root = createTree(arr);\r\n String s = serialize(root);\r\n display(deserialize(s));\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"1 3 5 null 6 null null 2 null 4 null null","sampleOutput":"1 -> 3 2 4 \r\n3 -> 5 6 \r\n5 -> \r\n6 -> \r\n2 -> \r\n4 -> \r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"0c0daf13-c06a-4f84-a818-516cce1183de","name":"Serialize And Deserialize N - Ary Tree","slug":"serialize-and-deserialize-n-ary-tree","type":1}],"next":{"id":"4d442c4e-50c1-4076-983c-119844c4040d","name":"Serialize And Deserialize N - Ary Tree","type":0,"slug":"serialize-and-deserialize-n-ary-tree"},"prev":{"id":"391337ec-064f-47d9-922d-4992bcffa7bd","name":"Serialize And Deserialize Binary Tree","type":0,"slug":"serialize-and-deserialize-binary-tree"}}}
plane

Editor


Loading...

Serialize And Deserialize N - Ary Tree

medium

1. Serialization is to store tree in a file so that it can be later restored. 2. The structure of tree must be maintained. Deserialization is reading tree back from file.

Constraints

0 <= Number of Nodes <= 10^5 -1000 <= value of Node data <= 1000

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

1 3 5 null 6 null null 2 null 4 null null

Sample Output

1 -> 3 2 4 3 -> 5 6 5 -> 6 -> 2 -> 4 ->

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode