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

Trees that keep values sorted

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

  1. You insert the values 40, 20, 60, 10, 30, 50, 55 in that order into an empty binary search tree. Which value becomes the root?

    • 20
    • 60
    • 10
    • 40

  2. Insert 6, 3, 9, 4, 1, 7, 8 into an empty binary search tree. Which becomes the root?

    • 3
    • 6
    • 9

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

    Answer: ______________

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

    • 1
    • 9
    • 4

  5. In the tree built by inserting 40, 20, 60, 10, 30, 50, 55 in that order, how many comparisons does it take to find the value 10, counting the comparison at every node you visit?

    Answer: ______________

  6. Using the same insert order, 40, 20, 60, 10, 30, 50, 55, what becomes the right child of the node holding 20?

    • 30
    • 10
    • 60
    • 40

  7. Insert 2, 4, 6, 8, 10, 12, 14 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 7 land?

    • Right child of 4
    • Left child of 6
    • Left child of 9

  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. 40 · The first value inserted into an empty tree always becomes the root, since there is nothing yet to compare it against.
  2. 6 · The first value has no node to compare against.
  3. 4 · The search visits 6, then 9, then 7, then 8.
  4. 4 · 4 moves left past 6, then right past 3.
  5. 3 · Searching for 10 visits the root 40, then 20, then 10 itself, one comparison at each stop.
  6. 30 · 30 is smaller than the root 40, so it moves left to node 20. Then 30 is larger than 20, so it becomes 20'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 9 · 7 is larger than 6 and smaller than 9.
  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