The locate methods from Ordered Vectors and Binary Search Trees are very similar. They have, for example, similar best-case behaviors. Explain why their behaviors differ in the worst case. Prove that,...

The locate methods from Ordered Vectors and Binary Search Trees are very similar. They have, for example, similar best-case behaviors. Explain why their behaviors differ in the worst case.

Prove that, if values are distinct, any binary search tree can be constructed by appropriately ordering insertion operations.