6: Binary Trees 6.1 Binary Trees 1. Draw a good sized binary tree. 2. Label the nodes of your drawing with their depth. 3. Label the nodes by the order they are processed in a preorder traversal. 4. Label the nodes by the order they are processed in an inorder traversal. 5. Label the nodes by the order they are processed in a postorder traversal 6. Label the nodes of your tree with the sizes of their subtrees 7. What kind of traversal would you do to compute the sizes of all subtrees in a tree? 6.2 Binary Search Tree:s 1. Consider an array containing the integers 0,...,15 in sorted order. Illustrate the operation of binary search on a few (a) integer values and a few (b) non-integer values. 2. Draw a binary search tree containing (at least) 0,..,15 3. Show the search path for a value x in the tree and a value x' not in the tree 4. Insert some value x into the tree 5. Delete some value x from your tree (try this for external nodes, internal nodes with 1 child, and internal nodes with two children). 7: Treaps Choose a permutation of the values 0,...15. Draw the binary search tree that results from inserting the elements of your permutation in order. Are there other permutations that could have given the same search tree? 1. 2. Explain the relationship between quicksort and random binary search trees. 3. Define the heap property for how priorities are used to make a binary tree into a Treap. 4. Pick some random numbers po, ..., P1s, and draw the treap that contains 0,..,15 where pi gives the priority for number i Explain the relationship between random binary search trees and Treaps. Explain the relationship between insertion and deletion in a Treap. 5. 6