In this section we consider an extremely important and useful
category of tree structure--*binary trees* .
A binary tree is an *N*-ary tree for which *N* is two.
Since a binary tree is an *N*-ary tree,
all of the results derived in the preceding section apply to binary trees.
However, binary trees have some interesting characteristics
that arise from the restriction that *N* is two.
E.g., there is an interesting relationship between binary trees
and the binary number system.
Binary trees are also very useful for the representation of
mathematical expressions involving
the binary operations such as addition and multiplication.

Binary trees are defined as follows:

Definition (Binary Tree)Abinary treeTis a finite set ofnodeswith the following properties:The tree is called the

- Either the set is empty, ; or
- The set consists of a root,
r, and exactly two distinct binary trees and , .left subtreeofT, and the tree is called theright subtreeofT.

Binary trees are almost always considered to be
*ordered trees* .
Therefore, the two subtrees and are called the
*left* and *right* subtrees, respectively.
Consider the two binary trees shown in Figure .
Both trees have a root with a single non-empty subtree.
However, in one case it is the left subtree which is non-empty;
in the other case it is the right subtree that is non-empty.
Since the order of the subtrees matters,
the two binary trees shown in Figure are different.

**Figure:** Two Distinct Binary Trees

We can determine some of the characteristics of binary trees
from the theorems given in the preceding section by letting *N*=2.
E.g., Theorem tells us that
an binary tree with internal nodes contains *n*+1 external nodes.
This result is true regardless of the shape of the tree.
Consequently, we expect that the storage overhead of associated
with the empty trees will be *O*(*n*).

From Theorem we learn that
a binary tree of height has at most internal nodes.
Conversely, the height of a binary tree with *n* internal nodes
is at least .
I.e., the height of a binary tree with *n* nodes is .

Finally, according to Theorem ,
a binary tree of height has at most leaves.
Conversely, the height of a binary tree with *l* leaves
is at least .
Thus, the height of a binary tree with *l* leaves is

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.