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?

Solution 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
}

Solution 2

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

Solution 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

Solution 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).

Solution 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.

View more solutions

Comments

[svick]

Or in a TreeView component in a GUI application.

[bluenote10]

What about non-recursive traversals? It appears to me that it is much easier to traverse a tree non-recursively in pre-order compared to in-order/post-order, since it does not require to return to previous nodes.

[Joshua Taylor]

@bluenote10 Can you elaborate on what you mean? In pre-order, you still "return" to a node to process its right child after processing its left child. Sure, you could use a queue of "nodes not yet visited", but but that's really just trading implicit (stack) storage for an explicit queue. In all traversal methods, both left and right children have to be processed, which means that after doing one of them you must be "returning" to the parent.

[bluenote10]

@JoshuaTaylor: Yes, they are all the same complexity class, but if you look at typical implementations, post-order is a probably a bit more tricky.

[CodeYogi]

I think you are trying to say something important can you please explain the first half?

[Raphael]

@CodeYogi What specifically do you need explained?

[CodeYogi]

"Pre- and post-order relate to top-down and bottom-up recursive algorithms" I think you want to say that in the first case node is processed before calling any of the recursive methods and vice-versa in the latter one, right?

[Raphael]

@CodeYogi Yes, basically.

[albin]

Pre-order traverse gives the node values in a sequence of insertion. If you want to create a copy of the tree you need to traverse the source tree in this way. In-order traverse gives the sorted node values. As to post-order traverse you can use this method to delete entire tree cause it visits leaf nodes first.

[CodeYogi]

I think its true even if the tree is not ordered right, I mean in order would not give the sorted sequence if the sequence was not sorted at first.

[markckim]

this is a great, concise answer and helped me understand pre-order and post-order use cases. although, it may be obvious given that the question mentions this directly, but note that this is the case for binary SEARCH trees and does not necessarily work for general binary trees. for example, you cannot necessarily use pre-order traversal to copy a general binary tree, as insertion logic during the copying process wouldn't work.

[rahil008]

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