Preorder Traversal of a Binary Tree

There are many ways of traversing a tree, depth first or breadth first. For depth first traversal, the most popular methods are inorder, preorder and postorder traversal. The rule for preorder traversal is:

1Process root, process left sub-tree, process right sub-tree

What does this rule mean for a binary tree? The figure below shows the recursive preorder traversal of all keys in the binary tree.

Pseudo-code for Preorder Traversal

The simplest algorithm for preorder traversal exploits the recursive structure of a binary tree. The easiest method is to write a recursive preorder traversal routine as given here.

You can go back and look at the figure to see how the preorder recursive routine is working.