Joe Celko's Trees and Hierarchies in SQL for Smarties

CHAPTER 7 Binary Trees

BINARY TREES ARE a special case of trees in which each parent can have, at most, only two children that are ordered (e.g., no children, a left child, a right child, or both a left and a right child). Binary trees are the subject of a lot of chapters in data structures books because they have such nice mathematical properties. For example, the number of distinct binary trees with (n) nodes is called a Catalan number, and it is given by the formula ((2n)!/((n + l)!n!)). Let’s stop and define some terms before we go any further.

Complete binary tree: a binary tree in which all leaf nodes are at level (n) or (n - 1), and all leaves at level (n) are toward the left, with “holes” on the right. There are between (2⁁(n - l)) ...