Serializing Using Preorder Traversal

We can modify the preorder routine to serialize a binary tree. All we need is a designated key to specify a null link. For this example, let's assume that we can only store zero or positive keys in the tree. Here, we can use -1 as a special key to denote a null link. The figure below shows the output array for the tree of our earlier example.

The pseudo-code for the serialization process is given below:

xxxxxxxxxx

Routine: treeToArray

Input: n = root of tree

Output: arrKeys: array of keys

​

Base case: n==null

1. arrKeys.add(-1)

​

Recursive case:

1. arrKeys.add(n.key);

2. treeToArray(n.left)

3. treeToArray(n.right)