Trees and Binary Search Trees · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Trees that keep values sorted

Computing · Algorithms & Data Structures · ages 17-18
Name ______________________   Date ____________

  1. You insert the values 5, 2, 8, 1, 3 in that order into an empty binary search tree. Which value becomes the root?

    • 2
    • 5
    • 8
    • 1

  2. Insert 5, 2, 8, 1, 3 into an empty binary search tree. Which becomes the root?

    • 2
    • 5
    • 8

  3. In that tree, how many comparisons find the value 3, counting every node visited?

    Answer: ______________

  4. With that same insert order, what becomes the right child of the node holding 2?

    • 1
    • 8
    • 3

  5. In the tree built by inserting 5, 2, 8, 1, 3 in that order, how many comparisons does it take to find the value 3, counting the comparison at every node you visit?

    Answer: ______________

  6. Using the same insert order, 5, 2, 8, 1, 3, what becomes the right child of the node holding 2?

    • 1
    • 3
    • 8
    • 5

  7. Insert 1, 2, 3, 4, 5, 6, 7 in order. What shape results?

    • A short bushy tree
    • A long one sided chain
    • Two separate roots

  8. In that tree, where does the value 1 land?

    • Right child of 8
    • Left child of 5
    • Left child of 2

  9. A student inserts 9 as the left child of 5. Which rule breaks?

    • Smaller left and larger right
    • One root per tree
    • No cycles allowed

  10. How does search cost in that chain compare with a bushy tree of seven?

    • Equal, shape never matters
    • Chain costs like a list, far more steps
    • Chain needs zero comparisons
LightMySky · lightmysky.comW1-mt_7PGHiAY54b-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Trees that keep values sorted W1-mt_7PGHiAY54b-s1

  1. 5 · The first value inserted into an empty tree always becomes the root, since there is nothing yet to compare it against.
  2. 5 · The first value has no node to compare against.
  3. 3 · The search visits 5, then 2, then 3.
  4. 3 · 3 moves left past 5, then right past 2.
  5. 3 · Searching for 3 visits the root 5, then 2, then 3 itself, one comparison at each stop.
  6. 3 · 3 is smaller than the root 5, so it moves left to node 2. Then 3 is larger than 2, so it becomes 2's right child.
  7. A long one sided chain · Every new value is larger, so each lands right of the last.
  8. Left child of 2 · 1 is smaller than 5 and smaller than 2.
  9. Smaller left and larger right · 9 is larger than 5, so it belongs on the right.
  10. Chain costs like a list, far more steps · Height sets comparisons, and the chain is tallest.
Worksheet · LightMySky