Traversal Concepts

Paths

Let's say we are given the tree shown.

We start at the root node (data = 20) and traverse through the tree.

There are many different possible "paths" through the tree as you can imagine.

                   20
                    |
      --------------+--------------
      |                           |
     10                          40
                            -----+
                            |
                           30

Three (Traversal) Action Options

Before we look at the three traversal paths, let's talk about the general concepts.

Sitting on the root (data = 20) node, what can we do?

We have three action options:

We traverse to the left
We traverse to the right
We can visit the current data (the "20")

                   20
                    |
      --------------+--------------
      |                           |
     10                          40
                            -----+
                            |
                           30

Traversing Left or Right

Traversing left or right simply means we move to the left or right.

For example, from the root node, if we "traverse right" that means we move to the node to the right (data = 40).

If the right child node is null, then for "traverse right" we would do nothing (no operation).

                   20
                    |
      --------------+--------------
      |                           |
     10                          40
                            -----+
                            |
                           30

Visiting

Visting means we go and visit the data of the node we are sitting on (the current node).

Again say we are at the root (data = 20). Then we would "visit" the 20.

What happens for the visit is coder's choice. For a simple visit scenario let's say we print to the console. Thus when we visit the (20) we simply print out the 20. And likewise for the other nodes (when we get to them during the traversal).

Other examples of "visiting" could be accumulating a sum, or sending each data element a message.

                   20
                    |
      --------------+--------------
      |                           |
     10                          40
                            -----+
                            |
                           30

Concepts Summary

When sitting at any given node, we have three action action options:

Action	Description
Traverse to Left	Traverse (move) to the node to the left (if null then no action)
Traverse to Right	Traverse (move) to the node to the right (if null then no action)
Visit Data	Visit the data at the current node (e.g. print the data)

                   20
                    |
      --------------+--------------
      |                           |
     10                          40
                            -----+
                            |
                           30

Traversal Type	Example Usages
Inorder	Visit nodes in non-decreasing order
Preorder	Copying Tree Prefix expression on of an expression tree
Postorder	Delete Tree (or subtree) Postfix expression of an expression tree