height

The number of edges on the longest path from a tree's root down to a leaf; a node's depth is its number of edges from the root.

In more detail

Search, insert and delete in a search tree all cost O(h), where h is the height, so keeping h small is everything. A balanced tree has height O(log n); a degenerate one has height n minus one. Nodes at the same depth form a level.

Related terms

Taught in

References