Exit Ticket: Binary Search Trees

Question 1: Search Trace

Given the BST below, which nodes are visited (in order) when searching for key 11?

A. 8 → 3 → 6 → 11 B. 8 → 12 → 10 → 11 C. 8 → 12 → 15 → 11 D. 8 → 12 → 11

Question 2: Insertion

Using the same tree above, if we insert key 9, where does it attach?

A. Left child of 10 B. Right child of 10 C. Left child of 11 D. Right child of 6

Question 3: Runtime

Why is the runtime of search and insert O(h)?

A. We visit every node in the tree B. We visit one node per level along a single root-to-leaf path C. We always visit exactly log(n) nodes D. We compare each node with every other node

Question 4: Deletion

When deleting a node with two children, what do we do?

A. Just remove the node and reconnect its children to the parent B. Replace it with its left child C. Find the in-order successor (min of right subtree), copy its key up, then delete the successor D. Delete the entire subtree and rebuild it

Question 5: Reflection

In one sentence: what is the BST invariant, and why does it make search efficient?

One sentence is enough.