Python Data Structures and Algorithms

Benefits of a binary search tree

We shall now briefly look at what makes a BST a better idea than using a list for data that needs to be searched. Let us assume that we have the following dataset: 5, 3, 7, 1, 4, 6, and 9. Using a list, the worst-case scenario would require you to search through the entire list of seven elements before finding the search term:

Searching for 9 requires six jumps.

With a tree, the worst-case scenario is three comparisons:

Searching for 9 requires two steps.

Notice, however, that if you insert the elements into ...