Preorder and Postorder Traversal of Rooted Trees

number of vertices

5

6

7

8

9

10

11

12

13

14

15

random tree

preorder = {3,1,2,4,5}

postorder = {1,2,4,5,3}

Many algorithms that make use of trees often traverse the tree in some order, that is, they visit each vertex in a systematic way. Two commonly used traversals are preorder and postorder. A preorder traversal of

T

is defined by a two-step recursion:

1. visit the root and

2. visit in preorder the subtrees of the root of

T

from left to right.

A postorder is similarly defined as:

1. visit in postorder the subtrees of

T

from left to right and

2. visit the root.

This Demonstration shows the preorder and postorder traversals corresponding to a randomly labeled rooted tree with a chosen number of vertices.