Serialize and Deserialize an N-ary Tree


  • 1
    R

    It was asked in Microsoft.

    It's similar to Serialize and Deserialize Binary Tree, but instead of binary tree, it's N-ary Tree.

    • You have an in-memory tree data structure. each node can have multiple children (can be more than 2). it's not search or balanced

    • You are sked to serialize it to a file so that you can deserialize it later with the same structure, node values can be any integers


  • 0

    Can a node has one child only?


  • 0

    Very interesting extension to the binary tree serialization/deserialization problem. Can you do it the BFS way? However you need to add some more information -- Probably how many children each node has (n), then follow by n nodes' values.


  • 0
    R

    @1337c0d3r Of course, thanks for the suggestion.


  • 0
    R

    @1337c0d3r Yes, it could range from 0 to N, I think the node structure could be something like:

    class TreeNode(object):
         def __init__(self, x):
             self.val = x
             self.children = []
    

  • 1

    I think serializing the n-ary tree using BFS this way might work:

            1 
          / | \
         2  3  4
           / \  \
          5   6  7
    

    can be serialized as:

    1, 1, 3, 2, 3, 4, 0, 2, 5, 6, 1, 7
    

    Deserializing it is easy. Here is the pseudocode:

    1. Read node count size: 1
      1. Read one node: 1.
      2. Insert node 1 into queue.
    2. Read node count size: 3
      1. Read three nodes: 2, 3, 4
      2. Pop node 1 from queue (parent), and insert three nodes (2, 3, 4) as children.
      3. Insert 2, 3, 4 into queue.
    3. Read node count size: 0
      1. Pop node 2 from queue.
    4. Read node count size: 2
      1. Pop node 3 from queue, insert 2 nodes (5, 6) as children.
        ... and so on, you get the idea.

  • 5

    1337c0d3r, your approach is very good. I would like to suggest another one using DFS. The tree above could be serialized as :
    (1(2)(3(5)(6))(4(7)))
    Serialization :
    Depth first search of the tree. Each root is serialized as (root serialize(child1) serialize(child2) ...serialize(childn))
    Deserialization :

    1. Read charcter.
      1.1 If it is ''(", new node is added to current parent in the tree. Push it to a stack. The newly inserted node becomes current parent.
      1.2 If it is '')", pop from the stack. Parent is updated.
      Here is code for serialization and deserialization
             public  TreeNode deserialize(StringBuilder in)  {
    		 TreeNode root = null;
    		 TreeNode parent = null;
    		 Stack<TreeNode> stack = new Stack<>();
    		 int pos = 0;
    		 while  (pos < in.length()) {
    			 if (in.charAt(pos) == '(')  {
                                    pos ++;
    				TreeNode node = new TreeNode(in.charAt(pos) -' 0');				
    				if (parent == null) 
    					root = node;			
    				else
    					parent.add(node);
    				stack.push(node) ;
    				parent = node;
    			 }
    			 else  if (in.charAt(pos) == ')')  {				
    				 stack.pop();
    				 if (!stack.isEmpty())
    					 parent = stack.peek();				
    			 }
    			 pos++;
    		 }
    		 return root;
               }	 
    
    	 public void serialize(TreeNode root, StringBuilder out)  {
    		 if  (root != null)  {
    			 out.append('(');
    			 out.append(root.val);
    			 for  (TreeNode child : root.getChildren())  {
    				 serialize(child, out);
    			 }
    			 out.append(')');
    		 }		 
    	 }
    

  • 0

    @elmirap This is very nice. Using parentheses to group nodes is a natural recursive representation of trees. If I am not mistaken, the nested level is the same as the depth of the node in the tree.


  • 0

    Did you implement deserialize iteratively using explicit stack on first attempt? Why do you choose to go this route?


  • 0

    @1337c0d3r Here is a reccursive solution of deserialize .My first attempt actually.

     TreeNode deserialize(StringBuilder in) {
    	 if  (0  <  in.length()) {			 
    	     if (in.charAt(0)  ==  '(') {
    		 in.deleteCharAt(0);
    		 TreeNode node = new TreeNode(in.charAt(0) - '0');
    		 in.deleteCharAt(0);
    		 while  (in.charAt(0)  !=  ')') {					 
    			 node.add(deserialize(in));	
    		 }		
    		 in.deleteCharAt(0);
    		 return node;
    		 }		 
    	  }
    	 return null;
     }
    

  • 0

    @elmirap I think it's pretty efficient. Mine is pretty much the same length as yours in 21 characters count. (You can ignore the first 1 because the root is implied 1 so we can skip the first two chars)

    Not sure how we can do it shorter than that, I guess we can compress the string :)


  • 0

    @1337c0d3r Maybe your approach is more efficient when we have parents with a lot of children (1000000) on one level, you will write 1000 000 and 1000 000 commas, but I have to transfer 2 parentheses per child - 2 000 000 parentheses .


  • 0

    @elmirap Good catch! Yes you are right. By the way you avoid recursion in deserialize, is it because you want to iterate the string in order?

    PS: It would be great if you can edit your post and edit the formatting of your code. It is kinda hard to read without it being formatted nicely.


  • 0

    @1337c0d3r , right, exactly. Recursion seemed to me a little complicated. Don't you think that none of both approaches have advantage in memory complexity?


  • 0

    @elmirap said in Serialize and Deserialize an N-ary Tree:

    @1337c0d3r , right, exactly. Recursion seemed to me a little complicated. Don't you think that none of both approaches have advantage in memory complexity?

    Not sure if I understood your question. Are you saying the space complexity of both BFS and DFS approaches are too high?


  • 0

    @elmirap said in Serialize and Deserialize an N-ary Tree:

    @1337c0d3r Here is a reccursive solution of deserialize .My first attempt actually.

     TreeNode deserialize(StringBuilder in) {
    	 if  (0  <  in.length()) {			 
    	     if (in.charAt(0)  ==  '(') {
    		 in.deleteCharAt(0);
    		 TreeNode node = new TreeNode(in.charAt(0) - '0');
    		 in.deleteCharAt(0);
    		 while  (in.charAt(0)  !=  ')') {					 
    			 node.add(deserialize(in));	
    		 }		
    		 in.deleteCharAt(0);
    		 return node;
    		 }		 
    	  }
    	 return null;
     }
    

    By the way, something strange acting in this forum. When I click on the quote link in your post, it is quoting content that is not visible on your post. Is this an edited post of yours? Seems like a bug to me.


  • 0

    @1337c0d3r I mean that we don't save a lot of memory when we implement "deserialize" iteratively, we use stack to store states, it is the same in recursive approach


  • 0

    @elmirap I see, sure. The recursion and stack approach both uses the same memory, the former uses implicit stack while the latter uses explicit stack.


  • 0

    I edited my comment, because I wanted to insert recursive approach too and later you quaoted it. Maybe it is a bug. Also I have to wait 120 seconds to write new comment, seems that the system wants to protect itself from bots, but it prevents me too from wrting too much :-)


  • 0

    Haha, I relaxed the restriction to 10 seconds now, is it low enough to encourage to write more? Not to mention that you are a writer btw :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.