Binary search tree

You already know what binary search is. Let's go back to the sorted array from an earlier chapter and study it again. If you think about binary search, you know you need to start from the middle of the sorted array. Depending on the value to be searched, either we return if the middle element is the search item, or move to the left or right based on whether the search value is greater than or less than the middle value. After this, we continue the same process recursively. This means the landing points in each step are quite fixed; they are the middle values. We can draw all the search paths as in the next figure. In each step, the arrows connect to the mid points of both the right half and left half, considering the current position. In the bottom part, we disassemble the array and spread out the elements while keeping the sources and targets of the arrows similar. As one can see, this gives us a binary tree. Since each edge in this tree moves from the midpoint of one...