4.1.1 Aside: Differing Definitions

The definitions in the previous section are the ones used in this book. They are the definitions that programmers often use in designing and implementing real programs. However, they are slightly different from the definitions used in formal computer science textbooks. This section gives these formal definitions and contrasts them against our own.

The most important difference is in the definition of a binary tree itself. Formally, a binary tree is either an “external node” or an “internal node” connected to a pair of binary trees called the internal node's left subtree and right subtree. Internal nodes correspond to our notion of nodes, and external nodes correspond roughly to nodes' empty left or right subtrees. The generic term “node” includes both internal and external nodes.

Every internal node always has exactly two children, although those children may be external nodes, so we must also revise definitions that depend on a node's number of children. Then, a “leaf” is an internal node with two external node children and a “nonterminal node” is an internal node at least one of whose children is an internal node. Finally, an “empty tree” is a binary tree that contains of only an external node.

Tree diagrams in books that use these formal definitions show both internal and external nodes. Typically, internal nodes are shown as circles, external nodes as square boxes. Here's an example BST in the format used in this book, shown alongside an identical BST in the format used in formal computer science books:

See also:  [Sedgewick 1998], section 5.4.