Binary Tree Traversal (PreOrder, InOrder, PostOrder) With Examples [Latest]

A Binary Tree is a data structure where every node has at most two children. We call the topmost node as the Root node.

Since it could have two children, we could move across the Binary Tree in different ways. Here, we will discuss the three most commonly used methods for traversal, namely:

• PreOrder Traversal
• InOrder Traversal
• PostOrder Traversal

Let us consider the below Binary Tree and try to traverse it using the above methods.

1. Binary Tree PreOrder Traversal

In a PreOrder traversal, the nodes are traversed according to the following sequence from any given node:

• It will mark the current node as visited first.
• Then, if a left child exists, it will go to the left sub-tree and continue the same process.
• After visiting the left sub-tree, it will then move to its right sub-tree and continue the same process.

Since the sequence is node -> left -> right, it is referred to as a PreOrder traversal, since the node is visited before the left sub-tree.

Let’s write the C/C++ code for this:

void preorder_traversal(Node* root) {
    if (root == NULL)
        return;
    printf("%d -> ", root->value);
    preorder_traversal(root->left);
    preorder_traversal(root->right);
}

PreOrder Traversal for our Binary Tree:

10 -> 20 -> 40 -> 50 -> 30 -> 60 -> 70

2. Binary Tree InOrder Traversal

In an InOrder traversal, the nodes are traversed according to the following sequence from any given node:

• If a left child exists, it will always go to it first.
• After it visits the left sub-tree, it will visit the currently given node
• After visiting the node, it will then move to its right sub-tree.

As the sequence is left -> node -> right, it will refer to it as an InOrder traversal, since we will visit the nodes “in order”, from left to the right.

The C/C++ code is given below

void inorder_traversal(Node* root) {
    if (root == NULL)
        return;
    inorder_traversal(root->left);
    printf("%dn", root->value);
    inorder_traversal(root->right);
}

InOrder Traversal for our Binary Tree:

40 -> 20 -> 50 -> 10 -> 60 -> 30 -> 70

3. Binary Tree PostOrder Traversal

In a PostOrder traversal, the nodes are traversed according to the following sequence from any given node:

• If a left child exists, it will always go to it first.
• After visiting the left sub-tree, it will then move to its right sub-tree.
• After it visits the right sub-tree, it will finally visit the currently given node

Since the sequence is left -> right -> node, it is referred to as a PostOrder traversal, since the nodes are visited at the last.

The C/C++ code is given below

void postorder_traversal(Node* root) {
    if (root == NULL)
        return;
    postorder_traversal(root->left);
    postorder_traversal(root->right);
    printf("%dn", root->value);
}

PostOrder Traversal for our Binary Tree:

40 -> 50 -> 20 -> 60 -> 70 -> 30 -> 10

4. Complete Implementation of Binary Tree Traversal in C/C++

To put it all together, I have put together the C/C++ code for all three traversals.

/**
    Code for https://journaldev.com article
    Purpose: Performs common Traversals on a Binary Tree
    @author: Vijay Ramachandran
    @date: 28-01-2020
*/
#include <stdio.h>
#include <stdlib.h>
// Define the types of Traversals here
enum Traversal {PREORDER, INORDER, POSTORDER};
typedef enum Traversal Traversal;
typedef struct Node Node;
// Define the Tree Node here
struct Node {
    int value;
    // Pointers to the left and right children
    Node* left, *right;
};
Node* init_tree(int data) {
    // Creates the tree and returns the
    // root node
    Node* root = (Node*) malloc (sizeof(Node));
    root->left = root->right = NULL;
    root->value = data;
    return root;
}
Node* create_node(int data) {
    // Creates a new node
    Node* node = (Node*) malloc (sizeof(Node));
    node->value = data;
    node->left = node->right = NULL;
    return node;
}
void free_tree(Node* root) {
    // Deallocates memory corresponding
    // to every node in the tree.
    Node* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}
void print_tree(Traversal traversal, Node* root) {
    // Prints the tree according to
    // various types of traversals
    if (!root)
        return;
    switch(traversal) {
        case (PREORDER):
            // Do a Preorder Traversal
            printf("%d -> ", root->value);
            print_tree(traversal, root->left);
            print_tree(traversal, root->right);
            break;
        case (INORDER):
            // Do an Inorder Traversal
            print_tree(traversal, root->left);
            printf("%d -> ", root->value);
            print_tree(traversal, root->right);
            break;
        case (POSTORDER):
            // Do a postorder Traversal
            print_tree(traversal, root->left);
            print_tree(traversal, root->right);
            printf("%d -> ", root->value);
            break;
    }
}
int main() {
    // Program to demonstrate finding the height of a Binary Tree
    // Create the root node having a value of 10
    Node* root = init_tree(10);
    // Insert nodes onto the tree
    root->left = create_node(20);
    root->right = create_node(30);
    root->left->left = create_node(40);
    root->left->right = create_node(50);
    root->right->left = create_node(60);
    root->right->right = create_node(70);
    printf("----Preorder Traversal:----n");
    print_tree(PREORDER, root);
    printf("nn");
    printf("----Inorder Traversal:----n");
    print_tree(INORDER, root);
    printf("nn");
    printf("----Postorder Traversal:----n");
    print_tree(POSTORDER, root);
    printf("nn");
    // Free the tree!
    free_tree(root);
    return 0;
}

Output

----Preorder Traversal:----
10 -> 20 -> 40 -> 50 -> 30 -> 60 -> 70 ->
----Inorder Traversal:----
40 -> 20 -> 50 -> 10 -> 60 -> 30 -> 70 ->
----Postorder Traversal:----
40 -> 50 -> 20 -> 60 -> 70 -> 30 -> 10 ->