Using the implementation of binary search tree operations we discussed in class, draw the trees that...

Transcribed Image Text:

Using the implementation of binary search tree operations we discussed in class, draw the trees that result from the following operations: (a) Inserting 142, 400, 205, 127, 100, 320, 160, 141, and 110 into an initially-empty tree (in that order). (b) Deleting 142 from the tree you drew for part (a). 4. (8 points) Draw the unique binary tree that has a preorder traversal of 4, 1, 6, 3, 7, 5, 9, 2, 8 and an inorder traversal of 6, 1, 7, 5, 3, 4, 9, 8, 2. Note that this will not necessarily be a binary search tree. 5. (a) (7 points) Consider the array of integers 523614 Draw the sequence of swaps that result from sorting this array using insertion sort. (b) (9 points) The following array contains a min-heap (a heap where each node is smaller than its children): 10 38 18 175 53 142 249 i. Draw this heap in tree format. ii. Show the array after each swap in the process of sorting it into decreasing order using heapsort. Using the implementation of binary search tree operations we discussed in class, draw the trees that result from the following operations: (a) Inserting 142, 400, 205, 127, 100, 320, 160, 141, and 110 into an initially-empty tree (in that order). (b) Deleting 142 from the tree you drew for part (a). 4. (8 points) Draw the unique binary tree that has a preorder traversal of 4, 1, 6, 3, 7, 5, 9, 2, 8 and an inorder traversal of 6, 1, 7, 5, 3, 4, 9, 8, 2. Note that this will not necessarily be a binary search tree. 5. (a) (7 points) Consider the array of integers 523614 Draw the sequence of swaps that result from sorting this array using insertion sort. (b) (9 points) The following array contains a min-heap (a heap where each node is smaller than its children): 10 38 18 175 53 142 249 i. Draw this heap in tree format. ii. Show the array after each swap in the process of sorting it into decreasing order using heapsort.