binary tree

1. Insert, into an empty binary search tree, entries with keys 3, 8, 20, 15, 30, 17, 5, 35, 19, 18, 16 (in this order). Draw this tree. Now delete 8 from the tree and draw the final tree. 2. Insert, into an empty AVL tree, entries with keys 3, 8, 20, 15, 30, 17, 5, 35, 19, 18, 16 (in this order). Draw the tree before and after each rebalancing step as well as the final tree. 3. Prove or disprove the claim that the order in which a fixed set of elements is inserted into a binary search tree does not affect the structure of the tree, i.e., that the same tree results no matter in which order the elements are inserted. 4. Prove or disprove the claim that the order in which a fixed set of elements is inserted into an AVL tree does not affect the structure of the tree, i.e., that the same tree results no matter in which order the elements are inserted. 5. Explain how to use an AVL tree to sort n comparable elements in O(n log n) time in the worst case.