Serialize and Deserialize n-ary tree

Given an N-ary Tree, Serialize and Deserialize it. Serialization is a basically a representation of a tree in a String format which takes much lesser space than storing the tree itself. Deserialization is constructing the actual tree using the serialized format of the tree. Following is an example of an N-ary Tree.

N-Ary Tree

Solution

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 deserialized to the original tree structure. Here we have encoded the tree as it’s value and the number of children it has in the next level.

Note:

  • N is in the range of [1, 1000].
  • Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

In an N-ary tree, there are no designated left and right children. An N-ary Tree is represented by storing an array or list of child pointers with every node.

import java.util.ArrayList;
import java.util.List;

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;
    }
}

Following is the serialization and deserialization implementation:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class SerializeAndDeserializeNAryTree {

    public String serialize(Node root) {
        if (root == null) {
            return "";
        }
        List<String> tree = new ArrayList<>();
        _serialize(root, tree);
        return String.join(",", tree);
    }

    private void _serialize(Node node, List<String> tree) {
        if (node == null) {
            return;
        }
        tree.add(String.valueOf(node.val));
        List<Node> children = node.children;
        int no_of_children = children == null ? 0 : children.size();
        tree.add(String.valueOf(no_of_children));
        if (children != null && !children.isEmpty()) {
            for (Node childNode : children) {
                _serialize(childNode, tree);
            }
        }
    }

    public Node deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        LinkedList<String> tree = new LinkedList<>(Arrays.asList(data.split(",")));
        Node node = _deserialize(tree);
        return node;
    }

    private Node _deserialize(LinkedList<String> tree) {
        int val = Integer.parseInt(tree.removeFirst());
        Node node = new Node(val);
        int size = Integer.parseInt(tree.removeFirst());
        if (size > 0) {
            List<Node> children = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                Node childNode = _deserialize(tree);
                children.add(childNode);
            }
            node.children = children;
        }
        return node;
    }
}

Categories: N-Ary 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