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

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 the 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?

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

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

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.

• Inorder Traversal prints out the nodes in sorted order if the given binary tree is a binary search tree. An example would if you need to find the k'th smallest element in a binary search tree:

      class Solution:
        def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
            res=None
            def inorder(node):
                if not node:
                    return
                # in bst this is the smallest value
                inorder(node.left)
                # python determines the scope at creation time of the function
                nonlocal k
                k-=1
                if k==0:
                    nonlocal res
                    res=node.val
                    return
                inorder(node.right)
            inorder(root)
            return res

• In Postorder we visit the left subtree and the right subtree before visiting the current node in recursion. An example would be if the given binary tree is height-balanced which is a binary tree in which the left and right subtrees of every node differ in height by no more than 1. In this case we have to get the height of left subtree and height of subtree and then pass the result to the parent node.

      class Solution:
        def isBalanced(self, root: Optional[TreeNode]) -> bool:
            def post_order(root):
                # leaf node is balanced
                if not root:
                    # we carry the height of each subtree
                    return [True,0]
                # with recursion, we start from bottom, so we do not have repetitive work
                left,right=post_order(root.left),post_order(root.right)
                # if any of the subtree return false, then we know entire tree is not balanced
                balanced=left[0] and right[0] and abs(left[1]-right[1])<=1
                # 1+max(left[1],right[1]) is the height of the each subtree. 1 is the root of the subtree
                return [balanced,1+max(left[1],right[1])]
            return post_order(root)[0]

• In Preorder we visit the current node first and then go to the left sub-tree. After touching every node of the left sub-tree, we will move towards the right sub-tree and visit in a similar fashion. An example would be constructing Binary Tree from Preorder and Inorder Traversal. In order to construct a tree we have to process the node first and then build its left and right

      class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
            if not preorder or not inorder:
                return None
            # first element of preorder is root
            root=TreeNode(preorder[0])
            # mid value in inorder gives us root. left values of root will be the left subtree, right values will be the right subtree
            # mid tells us how many elements we want from left subtree and howmany for right subtree
            mid = inorder.index(preorder[0])
            # we took 1 out of each array. preorder will not include the first, inorder will not include the mid value
            root.left=self.buildTree(preorder[1:mid+1],inorder[:mid])
            root.right=self.buildTree(preorder[mid+1:],inorder[mid+1:])
            return root

In-order : To get the original input string from any parse tree, because Parse tree follows the precedence of operators. The deepest sub-tree traversed first. So, the operator in the parent node has less precedence over the operator in the sub-tree.