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

These different forms now become possibilities to use for the recursive definition,
allowing you to construct even more kinds of trees:

* * * *

* * * * * * * *

* * * * * * * * * *

Using the recursive definition of a tree, we can define the concept of parent/child
relationships in the tree:

Parent/Child/Sibling/Ancestor/Descendant
For every node p that has a nonempty subtree with root node q , we say that
p is the parent of q and q is the child of p , which leads logically to ancestor
relationships (parent of parent of . . .), descendant relationships (child of
child of . . .), and sibling relationships (two nodes with the same parent).

Let us return to our original tree:

12

18 7

23 4 13

Let's start at the overall root node, which stores the value 12 . It has two nonempty
subtrees. The left subtree stores the value 18 at its root and the right subtree stores the
value 7 at its root. The nodes storing 18 and 7 are children of the node storing 12 and
they are siblings of each other. Similarly, the node storing 23 is a child of the node
storing 18 , and the nodes storing 4 and 13 are children of the node storing 7 , which
makes them descendants of the overall root. The overall root is the ancestor of each
of the other nodes.
Using this parent/child terminology, we can more precisely define our notion of
the overall root of the tree.

Root of a Tree (Overall Root)
The node at the top of a binary tree, the only node in the tree that has no
parent.

Another important aspect of binary trees is the distribution of nodes into different
levels of the tree. Our sample tree has three different levels: the overall root, the children