Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

6.21. Discussion Questions

1. Draw the tree structure resulting from the following set of tree function calls:

   >>> r = BinaryTree(3)
   >>> insert_left(r, 4)
   [3, [4, [], []], []]
   >>> insert_left(r, 5)
   [3, [5, [4, [], []], []], []]
   >>> insert_right(r, 6)
   [3, [5, [4, [], []], []], [6, [], []]]
   >>> insert_right(r, 7)
   [3, [5, [4, [], []], []], [7, [], [6, [], []]]]
   >>> set_root_val(r, 9)
   >>> insert_left(r, 11)
   [9, [11, [5, [4, [], []], []], []], [7, [], [6, [], []]]]
   

2. Trace the algorithm for creating an expression tree for the expression \((4 * 8) / 6 - 3\).

3. Consider the following list of integers: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Show the binary search tree resulting from inserting the integers in the list.

4. Consider the following list of integers: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Show the binary search tree resulting from inserting the integers in the list.

5. Generate a random list of integers. Show the binary heap tree resulting from inserting the integers on the list one at a time.

6. Using the list from the previous question, show the binary heap tree resulting from using the list as a parameter to the heapify method. Show both the tree and list form.

7. Draw the binary search tree that results from inserting the following keys in the order given: 68, 88, 61, 89, 94, 50, 4, 76, 66, and 82.

8. Generate a random list of integers. Draw the binary search tree resulting from inserting the integers on the list.

9. Consider the following list of integers: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Show the binary heap resulting from inserting the integers one at a time.

10. Consider the following list of integers: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Show the binary heap resulting from inserting the integers one at a time.

11. Consider the two different techniques we used for implementing traversals of a binary tree. Why must we check before the call to preorder when implementing it as a method, whereas we could check inside the call when implementing it as a function?

12. Show the function calls needed to build the following binary tree.

13. Given the following tree, perform the appropriate rotations to bring it back into balance.

14. Using the following as a starting point, derive the equation that gives the updated balance factor for node D.

You have attempted of activities on this page