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

Question

I realized recently that while having used BST's plenty in my life, I've never even contemplated using anything but Inorder traversal (while I am aware of and know how easy it is to adapt a program to use pre/post-order traversal).

Upon realizing this, I pulled out some of my old data-structures textbooks and looked for reasoning behind the usefulness of pre-order and post-order traversals - they didn't say much though.

What are some examples of when to use preorder/postorder practically? When does it make more sense than in-order?

Answer 1

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
}