Binary Tree Traversal - Pre-order, In-order, and Post-order

Introduction

It’s been almost a month since I set up this blog.

But… why can’t I write a single blog post!?

I really wanted to be a blogger, you know!

I decided to start writing technical posts. I’m currently studying binary trees, so let me share my understanding of Pre-order, In-order, and Post-order traversal!

Binary Tree Structure

To talk about the three traversal methods, we must first understand binary trees. Here’s the definition:

In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the “left subtree” and “right subtree”. Binary trees are commonly used to implement binary search trees and binary heaps.

We can see that binary trees are very useful, and their structure is:

Each node can have at most two child nodes
The tree starts from the root node and ends at external nodes (leaf nodes)

Pre-order, In-order, and Post-order

1. Pre-order

Now that we understand the structure, what is Pre-order traversal?

When searching all elements in a binary tree, we need to follow a pattern. The rules for Pre-order are:

First, we visit the root node - now we can do something with this node
Then we do the following in order: a) Visit the left child node, treating it as the new root, repeat steps 1-2 until no new nodes can be visited b) Visit the right child node, treating it as the new root, repeat steps 1-2 until no new nodes can be visited

This is clearly a recursive process. Here’s the code:

private void queryNodePreorder(ITree tree, IPosition nowRoot) {
    /* Do something with nowRoot */
    if (tree.isLeaf(nowRoot)) { // Exit recursion if leaf node
        return;
    } else {
        // Visit left and right children in order
        queryNodePreorder(tree, tree.getLeftChild(nowRoot)); 
        queryNodePreorder(tree, tree.getRightChild(nowRoot));
    }
}

2. In-order

In-order traversal is very similar to Pre-order. Here are the rules:

First, find the root node, but unlike Pre-order, we don’t visit it yet
Then we do the following in order: a) Find the left child node (don’t visit yet), treat it as the new root, repeat until we find the leftmost node b) Then start visiting from this node, after that visit its parent node c) After the parent, it’s the parent’s right child node d) Repeat steps a-c for the right child node until the entire tree is done

Here’s the code:

private void queryNodeInorder(ITree tree, IPosition nowRoot) {
    if (tree.isLeaf(nowRoot)) { // Exit recursion if leaf node
        return;
    } else {
        // Visit children in order
        queryNodeInorder(tree, tree.getLeftChild(nowRoot)); 
        /* Unlike Pre-order, we visit the node here */
        queryNodeInorder(tree, tree.getRightChild(nowRoot));
    }
}

3. Post-order

I’m not entirely sure why it’s called “Post-order”, but the principle is clear:

First, find the root node, but don’t visit it yet
Then do the following in order: a) Find the left child node, don’t visit b) Find the left child of that node, repeat until leaf node is found c) Visit that leaf node d) Visit the right child of the leaf’s parent e) Treat that right child as new root, repeat a-d f) After visiting the right child, visit the root node

Here’s the code:

private void queryNodePostorder(ITree tree, IPosition nowRoot) {
    if (tree.isLeaf(nowRoot)) { // Exit recursion if leaf node
        return;
    } else {
        // Visit children in order
        queryNodePostorder(tree, tree.getLeftChild(nowRoot)); 
        queryNodePostorder(tree, tree.getRightChild(nowRoot));
        /* Visit the node here */
    }
}

Summary

That’s it for this post! Pre-order, In-order, and Post-order - now you won’t confuse them anymore!

In the next post, I’ll talk about how to reconstruct a binary tree from Pre-order, In-order, and Post-order combinations. Hope I can keep it up!