Serialize and Deserialize Binary Tree

HARD

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Preorder serialization of the Binary Tree can be [1,2,null,null,3,4,null,null,5,null,null,]

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000

Solution

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

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return null;
        }
        StringBuilder treeBuilder = new StringBuilder();
        _serialize(root, treeBuilder);
        String codec = treeBuilder.toString();
        return codec;
    }
    
    private void _serialize(TreeNode node, StringBuilder treeBuilder){
        if(node == null){
           treeBuilder.append("null,");
            return;
        }
        treeBuilder.append(node.val).append(",");
        _serialize(node.left, treeBuilder);
        _serialize(node.right, treeBuilder);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.isEmpty()){
            return null;
        }
        LinkedList<String> nodeList = new LinkedList<>(Arrays.asList(data.split(",")));
        TreeNode root = _deserialize(nodeList);
        return root;
    }
    
    private TreeNode _deserialize(LinkedList<String> nodeList){
        String value = nodeList.removeFirst();
        if(value.equals("null")){
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = _deserialize(nodeList);
        node.right = _deserialize(nodeList);
        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));

Complexity Analysis

  • Time Complexity : In both serialization and deserialization functions, we visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes, i.e. the size of tree.
  • Space Complexity : In both serialization and deserialization functions, we keep the entire tree, either at the beginning or at the end, therefore, the space complexity is O(N).

Categories: Binary Tree

Tagged as: , , ,

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 )

Google photo

You are commenting using your Google 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