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.

xxxxxxxxxx

Routine: preorder

Input: n = root node of tree

​

Base case: n is null

1. if n==null

    return

​

Recursive case:

1. display n

2. preorder(n.left)

3. preorder(n.right)