1. the preorder traversal of a binary tree is “a b c d e f g h i,” while its inorder traversal is “c d e b f a i h g.” draw the corresponding the tree.

2. for the set of keys {1,4,5,10,16,17,21} give the sequence of key insertions so the final tree has height 2, 3, 4, 5, and 6, respectively. how many comparisons need to be performed by the operation lookup(21) in each of these cases?