Saturday, 26 September 2020

Serialize and Deserialize N-ary tree in Java

Serialize and Deserialize N-ary tree in java

This is a popular interview question asked in Tier-1 companies.

Given an n-ary tree, serialize and deserialize it.

Example of N-ary tree Serialization-Deserialization.

Serialize and Deserialize N-ary Tree

Algorithm

Serialization and Deserialization of N-ary tree is very similar to Serialization and Deserialization of Binary tree.

I would recommend to visit the Serialization/Deserialization post if not visited before: Serialize and Deserialize a Binary Tree

In Binary tree since there are only 2 child, we can get where is the start and end of the child of a particular Node from the serailized key, but in N-ary tree a Node can have n children, so we need some method to identify the start and end of a child nodes.

In this approach we will do a preorder traversal of N-ary tree and place the length of child nodes next to Node value as shown in example below,
 
serialize and deserialize n-ary tree implementation


In Deserialization process, it is exactly reverse now, we know first key in the String is the actual node and next key is the length of child nodes of a key.

Java Program to Serialize Deserialize N-ary tree

package javabypatel;

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

public class SerializeDeserializeNAryTree {

    public static void main(String[] args) {
        NAryNode root = new NAryNode(1,
                Arrays.asList(
                        new NAryNode(2, Arrays.asList(
                                new NAryNode(5),
                                new NAryNode(6),
                                new NAryNode(7, Arrays.asList(
                                        new NAryNode(11),
                                        new NAryNode(12))))),
                        new NAryNode(3),
                        new NAryNode(4, Arrays.asList(
                                new NAryNode(8),
                                new NAryNode(9),
                                new NAryNode(10)))
                ));

        String str = serializeTree(root, new StringBuilder());
        System.out.println(str);
        NAryNode deserializeRoot1 = deserializeApproach1(str == null? null : str.split(","), new int[1]);
        NAryNode deserializeRoot2 = deserializeApproach2(str);

        System.out.println(deserializeRoot1);
        System.out.println(deserializeRoot2);
    }

    //In this approach, we need to take a separate index array of size 1 to remember the next element in array to pick
    //or we can take a static integer to remember the state.
    private static NAryNode deserializeApproach1(String[] arr, int[] index) {
        if (arr == null || index[0] >= arr.length || arr[index[0]] == null) {
            return null;
        }

        NAryNode n = new NAryNode(Integer.parseInt(arr[index[0]++]));
        int size = Integer.parseInt(arr[index[0]++]);
        n.child = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            n.child.add(deserializeApproach1(arr, index));
        }
        return n;
    }

    //In this approach, we are converting serialized tree to Queue, so that when we do
    //queue.poll it will remove the element and we don't need to keep track of the next element to process.
    private static NAryNode deserializeApproach2(String str) {
        if (str == null) {
            return null;
        }
        return deserializeHelper(new LinkedList<String>(Arrays.asList(str.split(","))));
    }

    private static NAryNode deserializeHelper(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }

        NAryNode n = new NAryNode(Integer.parseInt(queue.poll()));
        int size = Integer.parseInt(queue.poll());
        n.child = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            n.child.add(deserializeHelper(queue));
        }
        return n;
    }

    private static String serializeTree(NAryNode root, StringBuilder sb) {
        if (root == null) {
            return null;
        }

        sb.append(root.data);
        sb.append(",");

        if (root.child != null) {
            sb.append(root.child.size());
            sb.append(",");
            for (int i = 0; i<root.child.size(); i++) {
                serializeTree(root.child.get(i), sb);
            }
        } else {
            sb.append(0);
            sb.append(",");
        }
        return sb.toString();
    }
}
NAryNode.java
package javabypatel;

import java.util.List;

public class NAryNode {
    public int data;
    public List<NAryNode> child;

    public NAryNode(int data, List<NAryNode> child) {
        this.data = data;
        this.child = child;
    }
    public NAryNode(int data) {
        this.data = data;
    }
}
at

No comments:

Post a Comment