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
}

Answer 2

Pre-Order / In-order /Post-order Usage : Simple words

Pre-order: Used to create a copy of tree Example : If you want to create a replica of a tree and need node values in an array and when you insert those values from index 0 to end in a new tree, you get a replica

In-order: : To get values of node in non-increasing order

Post-order: : When you want to delete a tree from leaf to root

Answer 3

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

Answer 4

Pre- and post-order relate to top-down and bottom-up recursive algorithms, respectively. If you want to write a given recursive algorithm on binary trees in an iterative fashion, this is what you will essentially do.

Observe furthermore that pre- and post-order sequences together completely specify the tree at hand, yielding a compact encoding (for sparse trees a least).

Answer 5

There are tons of places you see this difference play a real role.

One great one I'll point out is in code generation for a compiler. Consider the statement:

x := y + 32

The way you would generate code for that is (naively, of course) to first generate code for loading y into a register, loading 32 into a register, and then generating an instruction to add the two. Because something has to be in a register before you manipulate it (let's assume, you can always do constant operands but whatever) you must do it this way.

In general, the answers you can get to this question basically reduce to this: the difference really matter when there is some dependence between processing different parts of the data structure. You see this when printing the elements, when generating code (external state makes the difference, you can view this monadically as well, of course), or when doing other types of calculations over the structure that involve computations depending on the children being processed first.