Serialize and Deserialize Binary Tree, then Extend to N-ary Tree

Problem: Serialize and Deserialize a Binary Tree, then Extend to an N-ary Tree Implement tree serialization and deserialization. Part 1: Binary Tree Given a binary tree, implement: serialize(root): convert the binary tree into a string; deserialize(data): restore the original binary tree from the string. After serializing and deserializing, the tree structure and node values must remain exactly the same. For testing, use the following format: preorder traversal; use # for null nodes; separate tokens by spaces. Example: 1 / \ 2 3 / \ 4 5 Serialized as: 1 2 # # 3 4 # # 5 # # Part 2: Follow-up: N-ary Tree Extend the solution to an N-ary tree. Each node may have any number of children. For testing, use the following format: preorder traversal; each non-null node is represented as value:child_count; child_count is the number of direct children of the node; use # for an empty tree; separate tokens by spaces. Example: 1 / | \ 2 3 4 / \ 5 6 Serialized as: 1:3 2:0 3:2 5:0 6:0 4:0 Input Format The first line is the tree type: binary: binary tree; nary: N-ary tree. The second line is the serialized string in the corresponding format. Output Format The program should: deserialize the input string into a tree; serialize the tree again; print the serialized string. Constraints Number of nodes: 0 <= n <= 10^5; Node values are strings without spaces; The binary tree input is guaranteed to be a valid preorder sequence; The N-ary tree input is guaranteed to be a valid preorder sequence using value:child_count. Example Input binary 1 2 # # 3 4 # # 5 # # Output 1 2 # # 3 4 # # 5 # #