1) Now, suppose this is a new tree and insertions are done in this order: TreeNode * tree = NULL; insert(1, &tree); insert(3, &tree); insert(4, &tree); insert(6, &tree); insert(7, &tree); insert(8, &tree); insert(9, &tree); a) What does this tree look like?

b. Give an insertion order of the same nodes that results in a full (complete) BST where most interior nodes have two children. Show the tree that results from this insertion order.