PROBLEM DESCRIPTION
Serialization is to store a tree in an array so that it can be later restored and deserialization is reading tree back from the array. Complete the functions
- serialize() : stores the tree into an array a and returns the array.
- deSerialize() : deserializes the array to the tree and returns the root of the tree.
Note: Multiple nodes can have the same data and the node values are always positive integers. Your code will be correct if the tree returned by deSerialize(serialize(input_tree)) is same as the input tree. Driver code will print the in-order traversal of the tree returned by deSerialize(serialize(input_tree))
SOLUTION
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
class Tree {
// Function to serialize a tree and return a list containing nodes of tree.
public ArrayList<Integer> serialize(Node root) {
return serializeHelper(root, new ArrayList<>());
}
public ArrayList<Integer> serializeHelper(Node root, ArrayList<Integer> preorder){
if(root == null){
preorder.add(-1);
return preorder;
}
preorder.add(root.data);
serializeHelper(root.left, preorder);
serializeHelper(root.right, preorder);
return preorder;
}
// Function to deserialize a list and construct the tree.
public Node deSerialize(ArrayList<Integer> A) {
if(A.get(0) == -1){
A.remove(0);
return null;
}
Node node = new Node(A.get(0));
A.remove(0);
node.left = deSerialize(A);
node.right = deSerialize(A);
return node;
}
};
SMALL OPTIMIZATION
We can avoid removing elements from the list during deserialization by using an index variable.
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
class Tree {
// Function to serialize a tree and return a list containing nodes of tree.
public ArrayList<Integer> serialize(Node root) {
return serializeHelper(root, new ArrayList<>());
}
public ArrayList<Integer> serializeHelper(Node root, ArrayList<Integer> preorder){
if(root == null){
preorder.add(-1);
return preorder;
}
preorder.add(root.data);
serializeHelper(root.left, preorder);
serializeHelper(root.right, preorder);
return preorder;
}
// Function to deserialize a list and construct the tree.
public Node deSerialize(ArrayList<Integer> A) {
return deSerializeHelper(A, new int[]{0});
}
public Node deSerializeHelper(ArrayList<Integer> A, int[] idx){
if(idx[0] >= A.size() || A.get(idx[0]) == -1){
idx[0]++;
return null;
}
Node node = new Node(A.get(idx[0]));
idx[0]++;
node.left = deSerializeHelper(A, idx);
node.right = deSerializeHelper(A, idx);
return node;
}
};