Understanding the impact of height on performance

The height of a binary search tree is a critical property. Although we have not yet implemented operations on a binary search tree, the operations we will see later (search, insert, delete) all walk down a single root-to-leaf path, so their cost grows with the tree's height. There can be many tree representations for any given set of N values (where N is the number of 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.