Binary Trees - Building Java Programs: A Back to Basics Approach - page 980

root node

left
subtree

right
subtree

This recursive definition will be a useful way to think about trees as we write
binary tree code. The definition will help us to more precisely define the concepts of
a branch node and a leaf node.

Branch (Branch Node)
A node that has one or more nonempty subtrees.

Leaf (Leaf Node)
A node that has two empty subtrees.

Using our recursive definition, let's explore how we can form various kinds of
trees. The simplest kind of tree is an empty tree, which can't really be drawn because
it contains no values.
Once you understand the concept of an empty tree, you can use the second part of
the definition to create a new kind of tree that is composed of a root node with left
and right subtrees that are both empty. In other words, that tree would be a single leaf
node, which you could represent with a star:

*

Now you can use the recursive rule to say that a tree can be a root node with a left
tree that is empty and a right tree that is a leaf:

*

*

Or a tree can have an empty right and a leaf to the left:

*

*

Or a tree can have a leaf on either side:

*

* *