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:



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)


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){
        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){
                return null;
            Integer value = Integer.parseInt(nodes.get(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:


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


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

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading