Understanding the impact of height on performance

The height of a binary search tree is a critical property. So far, all the operations we have seen depend critically on the tree's height. There can be many tree representations for any given tree with N nodes. Not all tree representations are the same, however. To understand better how the height and number of nodes are related, let us look at all possible trees that can be created with just four nodes.

Some tree structures perform better than others regarding basic operations like search, insert, and delete.