When to use Preorder, Postorder, and Inorder Binary Search Tree Traversal strategies

When to use Pre-Order, In-Order, and Post-Order Traversal Strategy

Before you can understand under what circumstances to use pre-order, in-order and post-order for a binary tree, you have to understand exactly how each traversal strategy works. Use the following tree as an example.

The root of the tree is 7, the left most node is 0, the right most node is 10.

Pre-order traversal:

Summary: Begins at the root (7), ends at the right-most node (10)

Traversal sequence: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

In-order traversal:

Summary: Begins at the left-most node (0), ends at the rightmost node (10)

Traversal Sequence: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Post-order traversal:

Summary: Begins with the left-most node (0), ends with the root (7)

Traversal sequence: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

When to use Pre-Order, In-order or Post-Order?

The traversal strategy the programmer selects depends on the specific needs of the algorithm being designed. The goal is speed, so pick the strategy that brings you the nodes you require the fastest.

1. If you know you need to explore the roots before inspecting any leaves, you pick pre-order because you will encounter all the roots before all of the leaves.

2. If you know you need to explore all the leaves before any nodes, you select post-order because you don't waste any time inspecting roots in search for leaves.

3. If you know that the tree has an inherent sequence in the nodes, and you want to flatten the tree back into its original sequence, than an in-order traversal should be used. The tree would be flattened in the same way it was created. A pre-order or post-order traversal might not unwind the tree back into the sequence which was used to create it.

Recursive Algorithms for Pre-order, In-order and Post-order (C++):

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}

Pre-order: Used to create a copy of a tree. For example, if you want to create a replica of a tree, put the nodes in an array with a pre-order traversal. Then perform an Insert operation on a new tree for each value in the array. You will end up with a copy of your original tree.

In-order: : Used to get the values of the nodes in non-decreasing order in a BST.

Post-order: : Used to delete a tree from leaf to root

If I wanted to simply print out the hierarchical format of the tree in a linear format, I'd probably use preorder traversal. For example:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G