A binary tree t is either empty or consists of an element, called the root element, and
two distinct binary trees, called the left subtree and right subtree of t. This is a recursive
definition, and there are recursive definitions for many of the related terms:
height, number of leaves, number of elements, two-tree, full tree, and so on. The
interrelationships among some of these terms is given by the binary tree theorem.
For a binary tree t, the external path length of t, written E(t), is the sum of the
distances from the root to the leaves of t. A lower bound for comparison-based sorting
algorithms can be obtained from the external path length theorem.
There are four commonly used traversals of a binary tree: inOrder (recursively:
left subtree, root item, right subtree), postOrder (recursively: left subtree, right subtree,
root item), preOrder (recursively: root item, left subtree, right subtree), and
breadth-first (that is, starting at the root, level-by-level, and left-to-right at each level).
