4. *Efficiency in search trees*. What does it cost to find something in a binary search tree? - In the worst-case scenario, the cost is proportional to the length of the path from the root to the *most distant* leaf. - In the best-case scenario, the cost is proportional to the length of the path from the root to the *closest* leaf. Computer scientists worry about worst-case scenarios. To understand the worst-case scenario in a non-empty binary tree, we can compute the ratio of the *longest* root-to-leaf path to the *shortest* root-to-leaf path. This ratio is called the *path ratio*. (The path ratio of an empty tree is defined to be 1.) The closer the path ratio is to 1, the more efficient the tree is, both in the worst case and on average. The best practice in sophisticated search trees is to maintain a path ratio of at most 2. The two figures show binary search trees with path ratios of 1 (every path has length 2) and 3 (the longest path has length 3 and the shortest path has length 1). ![Tree with path ratio of 1](t1.png) ![Tree with path ratio of 3](t3.png) Solve the following problems: A. *Construct a data example* containing at least six nodes and having a path ratio of at most 2. - Use `check-expect` to be sure your data example is properly ordered. - In a comment, say how long is the *longest* path from the root to a leaf. - In a comment, say how long is the *shortest* path from the root to a leaf. A. *Define a function* that computes the path ratio of a binary-search tree. A. *Answer the following question*: when you convert the tree to an inorder list, then convert back to a tree, what happens to the path ratio? Why?