Main Page | See live article | Alphabetical index

Pre-order traversal

In Computer science, Pre-order traversal is used in Data structures, and specifically, Trees and Binary Trees.

Programs that utilize tree structures need to process nodes in a tree (represented as circles in below diagram). Nodes contain information about an object. For now, let's assume each node contains a letter.

Pre-Order Traversal is a type of Tree Traversal algorithm. Pre-order refers to when the root is processed previous to its two subtrees.

Steps to Preorder Traversal

Given a non-empty tree,

  1. Process the root
  2. Process the nodes in the left subtree with a recursive call
  3. Process the nodes in the right subtree with a recursive call

Given a binary tree PY:

The order would go A,B,D,E,G,C,F

Here is an example of Preorder in C++

int preorder_print(const binary_tree_nodes* ptr)
// ptr is a pointer to a node in a binary tree OR null
// meaning empty tree.
   if (ptr != NULL)
       std::cout << ptr->data() << std::endl;
       preorder_print( ptr->left() );
       preorder_print( ptr->right() );
   return 0;

The same example in
Haskell might look like

data Tree a = ET | Node(a, Tree a, Tree a)

preorder :: Tree a -> [a] preorder ET = [] preorder (Node (x, left,right)) = x : (preorder left) ++ (preorder right)

Compare: Inorder traversal, Post-order traversal