Let's don't waste time and finish the "confusing" topic of pre order, post order and in order traversal on binary trees. Most of my friends tell me that they often forget how each traversal works and ask me how to remember them. Well, here you go

When running through a tree (binary or binary search tree) we start from the root. Two things to do

• Add dummy nodes to the end of the leaf (Blue entry point in the image),
• Then after marking those go to the root and start traversing.

Now arrange the queue of nodes like this if we visit

• the node for the first time we add that to the pre-order queue,
• the node for the second time we add that to the in-order queue,
• the node for the 3rd time we add that to the post-order queue.

And now you have 3 queues each with pre-in-post order traversal path.

Also make a note that if the binary tree is a binary search tree, then the in-order traversal will give a sorted array. We can use this property to check if the binary tree is a binary search tree or not.

C Code

Let's see some C code for this traversal algorithm

Tree Structure

struct TreeNode {
    char data;
    struct TreeNode *left, *right;
};

typedef struct TreeNode TreeNode;

Traversal Algorithms

void inOrderTraversal(TreeNode *nodePointer){

    if (nodePointer != NULL) {
        inOrderTraversal(nodePointer->left);
        printf("%c", nodePointer->data);
        inOrderTraversal(nodePointer->right);
    }
}

void preOrderTraversal(TreeNode *nodePointer){

    if (nodePointer != NULL) {
        printf("%c", nodePointer->data);
        preOrderTraversal(nodePointer->left);
        preOrderTraversal(nodePointer->right);
    }
}

void postOrderTraversal(TreeNode *nodePointer){

    if (nodePointer != NULL) {
        postOrderTraversal(nodePointer->left);
        postOrderTraversal(nodePointer->right);

        printf("%c", nodePointer->data);
    }
}

More on this

To see the proper algorithm on this visit here

Get all the updates directly into your inbox by subscribing to the blog.