If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
Problem
Given a Generic 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 the serialized format of the tree.
OUTPUT:
Serialized Tree :
1 2 5 ) 6 ) ) 3 ) 4 7 ) 8 9 ) ) ) )
Deserialized Tree :
1 => [ 2 3 4 ]
2 => [ 5 6 ]
5 => [ ]
6 => [ ]
3 => [ ]
4 => [ 7 8 ]
7 => [ ]
8 => [ 9 ]
9 => [ ]
Solution
Serialization is just a traversal of the tree which can be either preorder or a postorder in which we insert an ‘end of subtree’ flag in the serialized string of the tree which helps us constructing the original tree while deserializing it.
SERIALIZATION:
We traverse in preorder in the tree and whenever we visit a new node we store it in the serialized string and in a set so that whenever we visit an already visited node we do not add in the serialized string.
whenever we return from a node, we append an end of subtree/child' flag in the string so that we keep a track on number of children / subtrees under that node.
DESERIALIZATION:
While deserializing the tree using the serialized string, we use a stack to keep the track of parent of the incoming node. So we will keep pushing the nodes into the stack until we get an ‘end of subtree’ marker, lets say we denote it by ‘)’, if we get ‘)’ , we pop a node from stack and make it the child of the node at top of the stack. We keep on doing the same until we are finished with the given serialized string of the tree and eventually the original tree will be constructed. We traverse once again in preorder to print the constructed tree.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
package GenericTree; import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; import java.util.Stack; public class serializeDeserialize { public static class Node { int data; ArrayList<Node> children; public Node(int data) { this.data = data; this.children = new ArrayList<>(); } } public static void main(String[] args) { Node[] nodes = new Node[10]; for (int node = 0; node < nodes.length; node++) { // initializing every node. nodes[node] = new Node(node); } // assuming first node as the root node. Node root = nodes[1]; // adding the children in the arraylist of every parent node. nodes[1].children.add(nodes[2]); nodes[1].children.add(nodes[3]); nodes[1].children.add(nodes[4]); nodes[2].children.add(nodes[5]); nodes[2].children.add(nodes[6]); nodes[4].children.add(nodes[7]); nodes[4].children.add(nodes[8]); nodes[8].children.add(nodes[9]); // this is where our serialized string will be stored. StringBuilder str = new StringBuilder(); serialize(root, new HashSet<>(), str); System.out.println("Serialized Tree : \n" + str); /*since we have the required information to represent * the tree therefore we can delete the actual tree * but since here we have to deserialize the tree also, * so we are reinitializing every node instead */ nodes = new Node[10]; for (int node = 0; node < nodes.length; node++) { nodes[node] = new Node(node); } deserialize(str.toString(), nodes); System.out.println("Deserialized Tree :"); printTree(root); } public static void serialize(Node node, HashSet<Integer> visited, StringBuilder str) { /* keeping the track of already visited node, * so that we only proceed with new nodes only */ visited.add(node.data); /*adding the node name to the serialized string */ str.append(node.data + " "); /*recurring for the children of the current node*/ for (Node child : node.children) { serialize(child, visited, str); } /*while returning back from recursion i.e. in post order * we will add an 'end of the subtree' flag*/ if (visited.contains(node.data)) { str.append(") "); } } public static void deserialize(String str, Node[] nodes) { Stack<Integer> stack = new Stack<>(); String[] tree = str.split(" "); for (String node : tree) { if (node.equals(")")) { /*if the current character is an 'end of the subtree' * flag, we pop a node from stack and make it the * child of the node which is at the top of stack * after popping this child out*/ int childNode = stack.pop(); if (stack.size() > 0) { int parentNode = stack.peek(); nodes[parentNode].children.add(nodes[childNode]); } } else { /* while traversing the serialized string * if we are currently on a node, we push * it directly to the stack without any * processing */ stack.push(Integer.parseInt(node)); } } } public static void printTree(Node node) { System.out.print(node.data + " => [ "); for (Node child : node.children) { System.out.print(child.data + " "); } System.out.print("] \n"); for (Node child : node.children) { printTree(child); } } } |
When you run above code, you will get below output
1 2 5 ) 6 ) ) 3 ) 4 7 ) 8 9 ) ) ) )
Deserialized Tree :
1 => [ 2 3 4 ] 2 => [ 5 6 ] 5 => [ ] 6 => [ ] 3 => [ ] 4 => [ 7 8 ]
Comment in case of any doubts or Edits, Happy Learning 🙂
