Serialize And Deserialize BST

Easy

Solve now

Problem statement

You are given a Binary Search Tree with its root node. You are supposed to serialize a binary search tree into a string and deserialize the string into a binary search tree.

Note :

Serialization is the process of converting an object into a stream of bytes.

Deserialization is the opposite process of creating an object from a stream of bytes.

You can apply your own serialization and deserialization algorithms.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image will be:

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format :

Print the level order traversal of the Binary Search Tree after Deserialization separated by spaces. It should match with the level order traversal of the initially given tree.

Print the answer of each test case in a new line.

Note :

None of the pointers in the new tree should point to nodes in the original tree, otherwise, the expected output can be different.

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N < 10^4
0 <= data < 10^4 and data!=-1

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to perform a recursive Preorder traversal and store the node values in a string separated by spaces. Here we are utilizing the property of the binary search tree, if we do a pre-order traversal of a binary search tree, we’ll get sorted values. For deserialization, first, create the left sub-tree, then create the right sub-tree and then return the root node.

The steps are as follows:

Serialization:

Define an empty string ‘serialized’ for storing the serialized string.
Define a recursive function ‘preOrderTraversal’, which takes two arguments root node of the tree, and the final string, ‘serialized’.
- If the root is null, then return from the function.
- If the size of the string is not zero ie. any value is already pushed into the string, then add a space in the string.
- Now, convert the node value into a string(using to_string in C++) and push it into the string ‘serialized’.
- Recursively call ‘helperForDeserialization’ for the left and the right sub-tree.
Return ‘serialized’ as the final answer.

Deserialization:

Here, we will use a string stream(for C++)(stringstream helps divide the string separated by spaces, commas, etc).
Define an empty array ‘allValues’, which stores all the node values of the tree from the given string.
The first step is to break the string into the node values using stringstream. It takes the given string, an empty string, and space as its arguments. It separates all the strings present in the given string separated by spaces.
A while loop is executed with the condition getline( It is a standard library function that reads a string or a line from the input stream).
- Push the string into the vector ‘allValues’ by converting it into an integer.
Initialize an integer ‘index’ to 0, which denotes the position that we are currently in the ‘allValues’ array.
Define a recursive function ‘helperForDeserialization’ which four arguments ‘allValues’, ‘index’, ‘minValue’, ‘maxValue’ which denotes the array containing all the node values, index at which we are currently, minimum node value for the current subtree, and the maximum node value for the current subtree.
- Base Conditions are when the index is out of the index, or the current node value is not satisfying the binary search tree properties i.e check whether it lies in the range (minimum value, maximum value), if not then return NULL.
- Make a tree node using the allValues[index] as the current root node.
- Recursively call the function ‘helperForDeserialization’ for the left and the right subtree by incrementing the index and after changing the maximum and the minimum values for the left and the right subtree.
- Return the ‘root’ as the answer to the current subtree.
Return the node returned by the function ‘helperForDeserialization’ as the answer.

Solve now

02 Approach

The idea is to get rid of the delimiters as they are consuming an extra space of 1 byte for every node value which is redundant.

Why is the previous approach taking more space?

It works fine for small integers but in the case of big integers, it will be a bit ineffective. For example, if the nodes to be stored in the form of string are“2 3 4”, it works fine. But in the case of big integers, let the string be “1111 2222 3333 4444”. Here, the string is consuming 15 bytes and if we can get rid of delimiters, it would consume 12 bytes. So, it is effective.

The idea is to store the integers in the form of 4-bit numbers as the maximum node value is 9999. For example, [1111, 2222, 3333, 4444] => “1111222233334444”, [2, 3, 4] => “xxx2xxx3xxx4”.

The rest of the steps are similar to the previous approach.

The steps are as follows:

Serialization:

Define an empty string ‘serialized’ for storing the serialized string.
Define a recursive function ‘preOrderTraversal’, which takes two arguments root node of the tree, and the final string, ‘serialized’.
- If the root is null, then return from the function.
- Here we are using 4 bytes for every node value. So, we will convert the integer node value into a 4 bytes character string.
- If the size of the string is not zero i.e. any value is already pushed into the string, then add a space in the string. Using the function ‘memcpy’, We can copy a block of memory from one location to another.
- Recursively call ‘helperForDeserialization’ for the left and the right sub-tree.
Return ‘serialized’ as the final answer.

Deserialization:

Here, we will convert the string to an integer using an ‘index’ variable(initialized to 0).
Define a recursive function ‘helperForDeserialization’ which takes a string ‘data’, ‘index’, minimum integer value, and maximum integer value as its argument, which denotes the input string, the current index, and boundaries of values for the current subtree(utilizing the property of the binary search tree). It returns the root node of the tree as output.
- Base condition is if ‘index’ is out of bounds, return NULL.
- Store the current value(allValues[index]) into an integer ‘value’.
- Now, check if ‘value’ satisfies the binary search tree properties or not i.e check whether it lies in the range (minimum value, maximum value). If it doesn’t satisfy, return NULL.
- Make the root node of the current subtree using node value ‘value’.
- Increment the index by 4(size of an integer) and recursively call ‘helperForDeserialization’ for the left and the right subtree after changing the maximum and the minimum values for the left and the right subtree.
- Return root as the root of the current subtree.
Return the node returned by the function ‘helperForDeserialization’ as the answer.