Serialize and Deserialize N-ary Tree

This page explains Java solution to problem Serialize and Deserialize N-ary Tree using Tree data structure.

Problem Statement

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 an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be de-serialized to the original tree structure.

Example 1:Input:

Output:
public String serialize(Node root)
Above function can serialize input tree as [1,3  3,2  5,0  6,0  2,0  4,0]

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class SerializeAndDeserializeNAryTree {
    // Encodes a tree to a single string.
    public String serialize(Node root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(Node root, StringBuilder sb) {
        if(root == null) {
            sb.append("NULL ");
        }
        else {
            int size = root.children.size();
            sb.append(root.val);
            sb.append(",");
            sb.append(size);
            sb.append(" ");

            for(Node child: root.children) {
                serialize(child, sb);
            }
        }
    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        String[] arr = data.split(" ");
        Queue<String> q = new LinkedList<>();
        for(String d: arr) q.offer(d);
        return deserialize(q);
    }

    private Node deserialize(Queue<String> q) {
        String e = q.poll();
        if(e.equals("NULL")) return null;
        else {
            String[] qArr = e.split(",");
            int val = Integer.parseInt(qArr[0]);
            int size = Integer.parseInt(qArr[1]);

            List<Node> children = new ArrayList<>();
            Node node = new Node(val, children);
            for(int i = 0; i < size; i++) {
                children.add(deserialize(q));
            }
            return node;
        }
    }
}

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

Time Complexity

O(N) Where
N is total number of elements in an input n-ary tree.

Space Complexity

O(N) Where
N is total number of elements in an input n-ary tree.