Serialize and Deserialize a Tree

Given the root node of a tree , serialize it into a string.

Given a serialized string , construct a tree and return the true node.

Try out the solution here:

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Solution:

Serialization:

First do a preorder traversal of the tree and store the node values in a string.

If node is null store the string value “null”.

Separate each value using a delimiter like “,” (comma)

Deserialization:

Convert the comma separated string value representing preorder traversal of the string into a list of string values.

Remove one value by one .(Use LinkedList since removal is faster for linked lists than array lists.

This way you will be constructing a node using the topmost value.

If the value is null return a null tree node.

Else construct a tree node using the first value , remove it.

And then construct the left sub tree using the remaining value recursively.

Also construct the right sub tree using the remaining value recursively.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    
    
    StringBuilder sb = new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
    
        return serializeNodes(root).toString();
  
        
    }
    
    public StringBuilder serializeNodes(TreeNode node){
        
        
        if(node==null){
            
            sb.append("null,");
            
                       }else{
        
      sb.append(String.valueOf(node.val)+",");
        
         serializeNodes(node.left);
        
        serializeNodes(node.right);
        }
        return sb;
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
        
        String[] nodes = data.split(",");
        
        List<String> nodeList = new LinkedList<String>(Arrays.asList(nodes));
        
        
        return deserializeNodes(nodeList);
        
    }
                                
        public TreeNode deserializeNodes(List<String> nodes){
                                    
    
            if(nodes.get(0).equals("null")){
                
                
                nodes.remove(0);
                
                return null;
            }
            
            
            Integer value = Integer.parseInt(nodes.get(0));
            nodes.remove(0);
            
            TreeNode node = new TreeNode(value);
            
            node.left = deserializeNodes(nodes);
                
                node.right = deserializeNodes(nodes);
                return node;
                                    
          }
    
    
    
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Time complexity:

We traverse through each node in both the cases so time complexity is O(n) where n is the number of nodes.

Space complexity:

Serialization:

For serialization we make n recursive calls so space complexity is O(n)

Deserialization:

Here again we make n recursive calls.

Also we create a new Tree of size n.

So total time complexity is O(2n), ignoring the constant it is O(n)

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s