Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 217

8.2 Binary Trees
A binary tree is a classic example of a nonlinear data structure—compare this to a linear list where we identify a first
item, a next item, and a last item. A binary tree is a special case of the more general tree data structure, but it is the
most useful and most widely used kind of tree. A binary tree is best defined using the following recursive definition:
A binary tree

a. is empty

or

b. consists of a root and two subtrees—a left and a right—with each subtree being

a binary tree

A consequence of this definition is that a node always has two subtrees, any of which may be empty. Another
consequence is that if a node has one nonempty subtree, it is important to distinguish whether it is on the left or right.
Here's an example:

A A

is a different binary tree from

B B

The first has an empty right subtree, while the second has an empty left subtree. However, as trees , they
are the same.
The following are examples of binary trees.
Here's a binary tree with one node, the root:

A

Here are binary trees with two nodes:

A F

C

B

Here are binary trees with three nodes:

A A

A A

B

B

C B

B

C C

C