Inorder traversal is a tree traversal algorithm that visits the nodes of a binary tree in an in-order fashion. This means that

• the left subtree of a node is visited
• then the root is visited
• finally the right subtree of a node is visited

C++ implementation of inorder traversal of trees:

#include <iostream>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Function to perform inorder traversal
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left);       // Traverse left subtree
    cout << root->val << " ";           // Process current node
    inorderTraversal(root->right);      // Traverse right subtree
}

int main() {
    // Create the binary tree
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);

    // Perform inorder traversal
    cout << "Inorder Traversal: ";
    inorderTraversal(root);
    cout << endl;



    return 0;
}

Output:

Inorder Traversal: 2 3 4 5 7 8 9

Explanation:

1.First we define the structure of a binary tree node. Each node has an integer value (val) and pointers to its left and right child nodes. The constructor initializes the node with a given value and sets the left and right pointers to nullptr.

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. To perform inorder traversal of the binary tree we use a function called inorderTraversal(). It takes a pointer to the root node as an argument and recursively traverses the left subtree, processes the current node's value, and then recursively traverses the right subtree. In this case, processing the node means printing its value.

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left);       // Traverse left subtree
    cout << root->val << " ";           // Process current node
    inorderTraversal(root->right);      // Traverse right subtree
}

3. In the main function it creates a binary tree by allocating memory for the nodes and setting their values. It sets up the tree structure by assigning appropriate left and right child nodes to each node.

Afterward, it calls the  inorderTraversal() function, passing the root node as an argument, to perform the inorder traversal. Finally, it prints the result, which is the inorder traversal of the tree.

int main() {
    // Create the binary tree
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);

    // Perform inorder traversal
    cout << "Inorder Traversal: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}