1. With a given binary search tree, you are asked to save the key of all the nodes into a file, then read the values one by one sequentially from the saved file and build a binary search tree that exactly replicates the original binary search tree.

Describe how you would do it and give an example of 5 nodes.

2.

Lets call an array Nums[0 . . 2n] plateau-valley if Nums[0] Nums[1] Nums[2] Nums[3] . . . Nums[2n-1] Nums[2n] (e.g. 3, 100, 50, 75, 33, 80, 17, 90, 60, 69, 11 )

Given a completely unsorted array [0 . . 2n] of numbers, describe an algorithm that is O(n) or better which takes the unsorted array as an input and returns a permutation of the array to result in a plateau-valley array.

(, 3 ) 169. (09)