degenerate tree

A search tree in which every node has only one child, so it is really a linked list with height n minus one.

In more detail

Inserting already sorted keys into a plain binary search tree produces one, and every operation becomes O(n). Shuffling the input or using a self-balancing tree avoids it.

Related terms

Taught in

References