We define binary trees recursively. A binary tree T is a structure defined on a finite set of nodes that either
- contains no nodes, or
- is composed of three disjoint sets of nodes: a root node, a binary tree called its left subtree, and a binary tree called its right subtree.
The binary tree that contains no nodes is called the empty tree or null tree, sometimes denoted NIL. If the left subtree is nonempty, its root is called the left child of the root of the entire tree. Likewise, the root of a nonnull right subtree is the right child of the root of the entire tree. If a subtree is the null tree NIL, we say that the child is absent or missing. Given Figure shows a binary tree
A binary tree is not simply an ordered tree in which each node has degree at most 2. For example, in a binary tree, if a node has just one child, the position of the child—whether it is the left child or the right child—matters. In an ordered tree, there is no distinguishing a sole child as being either left or right. Given Figure shows a binary tree that differs from the tree in Figure because of the position of one node. Considered as ordered trees, however, the two trees are identical.
We can represent the positioning information in a binary tree by the internal nodes of an ordered tree, as shown in Figure . The idea is to replace each missing child in the binary tree with a node having no children. These leaf nodes are drawn as squares in the figure. The tree that results is a full binary tree: each node is either a leaf or has degree exactly 2. There are no degree-1 nodes. Consequently, the order of the children of a node preserves the position information.