C++ Program to Perform Inorder, Preorder, and Postorder Traversal of a Binary Tree

1. Introduction

Binary tree traversal refers to the process of visiting all the nodes in a binary tree in a specific order. The most common traversal methods are inorder, preorder, and postorder. Understanding these traversal methods is essential, as they form the basis for many algorithms applied to binary trees. 

In this post, we will provide a C++ implementation of these three fundamental traversal methods.

2. Program Overview

Our program will:

1. Define a binary tree using a Node structure.

2. Implement functions for:

- Inserting elements into the tree.

- Performing inorder traversal.

- Performing preorder traversal.

- Performing postorder traversal.

3. Demonstrate these functions in the main program.

3. Code Program

#include<iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// Insert function for binary tree
Node* insert(Node* root, int data) {
    if (root == nullptr) {
        return new Node(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

// Inorder traversal
void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

// Preorder traversal
void preorder(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

// Postorder traversal
void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 12);
    root = insert(root, 18);

    cout << "Inorder Traversal: ";
    inorder(root);
    cout << endl;

    cout << "Preorder Traversal: ";
    preorder(root);
    cout << endl;

    cout << "Postorder Traversal: ";
    postorder(root);
    cout << endl;

    return 0;
}

Output:

Inorder Traversal: 3 5 7 10 12 15 18
Preorder Traversal: 10 5 3 7 15 12 18
Postorder Traversal: 3 7 5 12 18 15 10

4. Step By Step Explanation

1. We start by defining a Node class that represents each node in the binary tree. Each node has data, a left child, and a right child.

2. The insert function is a recursive function that inserts a new value into the tree, maintaining the properties of a binary search tree (BST).

3. The inorder, preorder, and postorder functions are recursive functions to traverse the tree in the respective order. They visit the nodes and print the data.

4. In the main function, we create a sample binary tree and demonstrate the three traversal methods.

Note: The program demonstrates traversals on a Binary Search Tree (BST) for simplicity. The traversal methods, however, apply to any binary tree.