CS111 C++ Practice Quiz #8

Binary Trees



  1. The first node of a tree is the ________________________ node.


  2. Each link in a tree node points to a(n) ________________________ or ________________________ of that node.


  3. A tree node that has no children is called a ________________________ node.


  4. Name the three traversal algorithms for traversing a binary search tree.
    • a. ________________________

    • b. ________________________

    • c. ________________________




  5. What are the advantages and disadvantages of using a Binary Search tree?







  6. Using the following sequence of input, build a binary search tree. 7, 5, 20, 4, 6, 19, 25, 30, 15, 3.







  7. For the binary search tree you just created, redraw the tree after deleting node 5.







  8. Redraw the tree one more time after deleting node 20.









Answers
  1. root
  2. child or subtree
  3. leaf
  4. a. inorder, b. preorder, and c. ostorder.
  5. The primary disadvantage of a binary search tree is that it may become very unbalanced, in which case searching degenerates into an O(n) algorithm. The advantage is the fact that it is very efficient for insertions and deletions.