1 / 6 Binary Search Trees, Rotations & Balance

Locally Fine Globally Broken

Every node below is on the correct side of its own parent: each left child is smaller than its parent, each right child is larger.

Each child is on the correct side of its own parent 40 20 60 10 55 50 70

You call the standard BST lookup, the one that compares against the current node and descends left or right, once for each of the seven keys.

Which lookups return "not found"?

A

None. Every key is reachable, the tree is just unbalanced.

B

55 only

C

55 and 50

D

50 only