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

Here are binary trees with all left subtrees empty and all right subtrees empty:

A A

B

B

C C

Here is a binary tree where each node, except the leaves, has exactly two subtrees; this is called a complete
binary tree:

C

G

E

D

B A

F

Here is a general binary tree:

C

E G

N

B A

F

K

J

H

8.3 Traversing a Binary Tree
In many applications, we want to visit the nodes of a binary tree in some systematic way. For now, we'll think of “visit”
as simply printing the information at the node. For a tree of n nodes, there are n ! ways to visit them, assuming that
each node is visited once.
For example, for a tree with the three nodes A, B, and C, we can visit them in any of the following orders: ABC,
ACB, BCA, BAC, CAB, and CBA. Not all of these orders are useful. We will define three ways—pre-order, in-order, and
post-order—that are useful.
This is pre-order t raversal :

1. Visit the root.

2. Traverse the left subtree in pre-order.

3. Traverse the right subtree in pre-order.

Note that the traversal is defined recursively. In steps 2 and 3, we must reapply the definition of pre-order
traversal, which says “visit the root, and so on.”