When to use in-order, pre-order, or post-order traversal?

Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

DFS can be perform the search using in-order, pre-order, or post-order traversal. Depending on the problem, one type of traversal may be more suitable than the others depending on the problem.

We will discuss the applications of each type of traversal, and when to use them.

Quickly find a node in a tree - Pre-order Traversal application #

A pre-order traversal is useful when the goal is to quickly find a node in a tree. This is because the algorithm will visit the children of a node before visiting the parent. This means that the algorithm will find the node as soon as it is visited, and will not need to visit any other nodes.

Consider the following tree:

       1(B)
     /      \
    2(A)     3(D)
   /    \
  4(E)   5(G)

If the goal is to find a node with value A, using pre-order traversal, the algorithm would first check node 1 for the value A, then node 2. The value A is found at node 2, so the search stops.

node 1 -> check node 1 
    -> node 2 -> check node 2 
        -> search completes

When using pre-order traversal, the algorithm would recurse to the left child node 2, and then to node 4. Since node 4 has no children, the algorithm would then check node 2 for the value A, and the search would stop. With in-order traversal, the search would be slower than with pre-order traversal, as it would visit more nodes before backtracing and finding the value A at node 2.

node 1 
    -> node 2 
        -> node 4 -> check node 4 
    -> backtrack to node 2 
        -> check node 2 
            -> search completes

Reverse Polish Notation - Postfix Traversal Application #

Postfix traversal appllications are for sceanrios where we need to visit the children first before visiting the parent. This is useful for mathematical expressions, where the children are the operands and the parent is the operator.

For example, the mathematical expression (2 * 1) + 3 can be represented as a tree:

       +
     /   \
    *     3
   /  \
  2    1

So the postfix traversal would be 2 1 * 3 +, which can be used for evaluating the expression, as the operands are visited before the operator.

Note that the postfix traversal is also known as the reverse polish notation (RPN), and must be used on a full binary tree. That is, each node must have either 0 or 2 children.

public int evaluate(Node node) {
    if (node.left == null && node.right == null) {
        return Integer.parseInt(node.value);
    }

    int left = evaluate(node.left);
    int right = evaluate(node.right);

    if (node.value.equals("+")) {
        return left + right;
    } else if (node.value.equals("-")) {
        return left - right;
    } else if (node.value.equals("*")) {
        return left * right;
    } else if (node.value.equals("/")) {
        return left / right;
    } else {
        return Integer.parseInt(node.value);
    }
}
    

Finding the Kth smallest element in a BST - In-order Traversal Application #

A BST, binary search tree, is a binary tree where the left child of a node is smaller than the parent, and the right child is larger.

In-order traversal is useful for finding the Kth smallest element in a binary search tree (BST). This is because the algorithm will visit the left child of a node before visiting the parent, and then the right child. This means that the algorithm will visit the smallest elements first, and then the larger elements.

Consider the following BST, composeed of 7 nodes, numbered from 1 to 7, with the values in parentheses.

          4(5)
       /       \
    2(3)       6(8)
   /    \      /   \
  1(1)   3(4) 5(6)   7(9)

A counter is used to keep track of the number of nodes visited.

If the goal is to find the 3rd (k = 3) smallest element in the BST, using in-order traversal, then the processing steps are.

• The algorithm would first visit the left child of node 4, then node 2, then the left child of node 2, which is node 1.

• Since node 1 has no left child, the counter is incremented to 1. Since node 1 has no right child, the algorithm would backtrack to node 2. The counter is incremented to 2, before visiting node 3.

• At node 3 there is no left child, so the counter is incremented to 3. The search stops at node 3, as the counter is equal to the value of k, and the value 4 is returned.

The Java code for finding the kth smallest element in a BST using in-order traversal is as follows.

int count = 0;

public int kthSmallest(Node node, int k) {
    if (node == null) {
        return 0;
    }

    int left = kthSmallest(node.left, k);
    if (left > 0) {
        return left;
    }

    count++;
    if (count == k) {
        return node.value;
    }

    return kthSmallest(node.right, k);
}