Deserialization Using Preorder Traversal

If we serialize using preorder traversal, we have to apply the same preorder procedure to recursively build the tree. We'll take the keys from the array one by one and build the tree accordingly. The routine arrayToTree takes two arguments, i.e., the array of keys and an index. The base case would be true either when index passed is out of bound or if the key at index position is -1. Calling the routine with arrkeys and index = 0, would return the root node. The figure below illustrates how the tree is built.

xxxxxxxxxx

Routine: arrayToTree

Input: arrKeys = array of keys, ind = index of array

Output: root node of binary tree

​

Base case 1: ind >= arrKeys.length

1. return null

​

Base case 2: arrKeys[ind] == -1

1. return null;

​

Recursive case:

1. n = create a new node with key = arrKeys[ind]

2. ind = ind+1;

3. n.left = arrayToTree(arrKeys,ind);

4. ind = ind+1;

5. n.right = arrayToTree(arrKeys,ind);

6. return n;