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++.

### 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.

```
#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:

```
1
/ \
2 3
/ \
4 5
```

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.

```
#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.

```
#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