Posts Serialize and deserialize a binary tree (geeksforgeeks - SDE Sheet)
Post
Cancel

Serialize and deserialize a binary tree (geeksforgeeks - SDE Sheet)

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))

geeksforgeeks

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;

    }

};
This post is licensed under CC BY 4.0 by the author.