CPP Program to Implement Inorder Traversal of a Binary Tree

In the world of computer science, trees are fundamental data structures used to model hierarchical relationships. Among the various types of tree traversals, the inorder traversal of a binary tree is particularly important. Inorder traversal visits the nodes of the tree in a specific order: left subtree, root, and then the right subtree. This traversal method is commonly used in binary search trees (BST) to retrieve the nodes in a sorted manner. Understanding and implementing inorder traversal is crucial for anyone looking to delve deeper into data structures and algorithms using C++.

Table of Contents

Prerequisites

Before we dive into the examples, there are a few prerequisites:

Basic understanding of C++ programming.
Knowledge of pointers and dynamic memory allocation.
Familiarity with the concept of a binary tree and its structure.

With these basics in place, let’s explore different implementations of inorder traversal.

1. Basic Implementation of Inorder Traversal

1.1 Program Structure

To implement inorder traversal in C++, we’ll first define the structure of a binary tree node and then write the function for the traversal itself.

C++

#include <iostream>

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

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

    inorderTraversal(root->left);
    std::cout << root->value << " ";
    inorderTraversal(root->right);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

1.2 Output Explanation

In this example, the binary tree is structured as follows:

C++

The inorder traversal of this tree will be: 4 2 5 1 3

2. Inorder Traversal Using Stack

2.1 Program Structure

In cases where recursion is not preferred, we can use an iterative approach with a stack to perform inorder traversal of a binary tree.

C++

#include <iostream>
#include <stack>

void inorderTraversal(TreeNode* root) {
    std::stack<TreeNode*> stack;
    TreeNode* current = root;

    while (current != nullptr || !stack.empty()) {
        while (current != nullptr) {
            stack.push(current);
            current = current->left;
        }

        current = stack.top();
        stack.pop();
        std::cout << current->value << " ";
        current = current->right;
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "Inorder Traversal (using stack): ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

2.2 Output Explanation

The binary tree structure remains the same, and the output of the inorder traversal using the stack is: 4 2 5 1 3

3. Inorder Traversal Using Morris Traversal

3.1 Program Structure

Morris Traversal is an advanced method that uses threading to traverse the tree without using additional space for recursion or stack.

C++

#include <iostream>

void inorderTraversal(TreeNode* root) {
    TreeNode* current = root;
    TreeNode* pre;

    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->value << " ";
            current = current->right;
        } else {
            pre = current->left;
            while (pre->right != nullptr && pre->right != current)
                pre = pre->right;

            if (pre->right == nullptr) {
                pre->right = current;
                current = current->left;
            } else {
                pre->right = nullptr;
                std::cout << current->value << " ";
                current = current->right;
            }
        }
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::cout << "Inorder Traversal (using Morris traversal): ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

3.2 Output Explanation

The binary tree structure is the same, and the output of the inorder traversal using Morris Traversal is: 4 2 5 1 3

Conclusion

Understanding “what is inorder traversal of a binary tree” is fundamental for anyone studying data structures. We’ve covered various implementations of inorder traversal in C++, including recursion, stack-based iteration, and Morris Traversal. Each method has unique advantages and trade-offs. For example, recursion is straightforward but can cause stack overflow on deep trees, while the stack-based method uses extra space but avoids recursion’s limitations. Morris Traversal is efficient in terms of space but is more complex to implement