Problem

Write a function for searching, using a binary search tree with sentinel as folsentinel search lows: Introduce a new sentinel node, and keep a pointer called sentinel to it. See Figure 10.11. Replace all the NULL links within the binary search tree with sentinel links (links to the sentinel). Then, for each search, store the target key into the sentinel node before starting the search. Delete the test for an unsuccessful search from tree_search, since it cannot now occur. Instead, a search that now finds the sentinel is actually an unsuccessful search. Run this function on the test data of the preceding project to compare the performance of this version with the original function tree_search.