Types of binary trees

Binary trees come in a few named shapes. The names show up constantly — in interview questions ("check whether a tree is complete"), in data structures (a heap is a *complete* tree), and in complexity arguments ("in a *balanced* tree this is O(log n)"). Here are the ones worth knowing, and the counting facts that come with them.

The shapes

And one that is about values, not shape: a binary search tree keeps everything in a node's left subtree smaller and everything in its right subtree bigger (previous lesson). A BST can have any of the shapes above — and its speed depends on which one.