Traversing a binary tree

There are three ways of traversing a tree:

• Pre-order traversal
• In-order traversal
• Post-order traversal

The name refer to whether the root of each sub-tree is visited before, between of after both branches have been traversed.

Pre-order traversal

Draw an outline around the tree structure, starting to the left of the root. As you pass to the left of a node (where the red dot is marked), output the data in that node.

The nodes will be visited in the sequence 17, 8, 4, 5, 12, 14, 22, 19, 30 ,25

A pre-order traversal may be used to produce prefix notation, used in functional programming languages. A simple illustration would be a function statement, x = sum a, b rather than x = a + b, in which the operation comes before the operations rather than between them, as in infix notation.

In-order traversal

Draw an outline around the tree structure, starting to the left of the root. As you pass underneath a node (where the red dot is marked), output the data in that node.

The nodes will be visited in the sequence 4, 5, 8, 12, 14, 17, 19, 22, 25, 30

The in-order traversal visits the nodes in sequential order.

Q3: Construct a binary search tree to hold the names Mark, Stephanie, Paul, Anne, Hanna, Luke, David, Vincent, Tom. List the names, in the order they would be checked, to find David.

Q4: List the names in the order they would be output when an in-order traversal is performed.

Post-order traversal

Draw an outline around the tree structure, starting to the left of the root. As you pass to the right of a node (where the red dot is marked), output the data in that node.

The nodes will be visited in the sequence 5, 4, 14, 12, 8, 19, 25, 30 ,22, 17

Post-order traversal is used in program compilation to produce Reverse Polish Notation.

Questions:

Exercises:

Ex 1. Traversal of a binary tree

Exam questions: