Problem Set: Trees


  1. What are the preorder, inorder, and postorder traversals of the tree shown above?
  2. Is the tree shown above a BST? If not, why not?
  3. Is the tree above balanced? If not, where is it out of balance?
  4. What is the level of the following nodes: G, W, and U?
  5. What is the height of the tree?
  6. Is the BST above balanced? If not, where is it out of balance?
  7. What is the height of the subtree rooted at G?
  8. What is the level of O? What is the level of J?
  9. Starting with the BST given above, show the tree after calling the delete method to delete each of the following items, in the order G, O, L.
  10. What are the preorder, inorder, and postorder traversals of the tree shown above?
  11. Is the tree shown above a BST? If not, why not?
  12. Starting with the BST given above, show the tree after calling the delete method to delete the following items, in the given order: 55, 95, 20, 75, 77, 100.
  13. Beginning with an empty BST, show the search tree that is formed when you insert the following values in the order given.
    1. W T N J E B A
    2. W T N A B E J
    3. B N A W J T E
    4. J N B A W E T
  14. Beginning with an empty BST, show the search tree that is formed when you insert the following values in the order given.
    1. 40 80 70 10 30 90 60 20 50
    2. 50 60 20 90 10 80 40 30 70
    3. 80 20 60 70 30 10 40 50 90
  15. Suppose a BST stores integers in the range 1 to 1000. Which of the following search sequences is not possible when searching for the value 410 in this tree?
    1. 620, 255, 350, 520, 480, 410
    2. 590, 400, 500, 300, 350, 410
    3. 100, 350, 600, 400, 500, 450
    4. 150, 200, 320, 300, 350, 400
  16. Suppose a BST stores integers in the range 1 to 1000. Which of the following search sequences is not possible when searching for the value 225 in this tree?
    1. 500, 355, 150, 320, 200, 225
    2. 500, 400, 200, 300, 200, 350, 225
    3. 50, 100, 600, 400, 40, 120
    4. 50, 500, 100, 400, 200, 300
  17. Write a method for the BST class (using recursion) to count the number of nodes in a BST.
  18. Write a method for the BST class (using recursion) to compute the height of a BST.
  19. Write a method for the BST class (using recursion) to find the maximum element in a BST.
  20. Write a method for the BST class (using recursion) that visits the nodes in reverse sorted order.
  21. Write a function (client code) to print out all the objects in a BST of Pet objects. Print the objects in sorted order. The parameter is the tree.

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2016