Lecture 286:- Iterative Inorder

Here's a C++ implementation of iterative inorder traversal for a binary tree using a stack:

cppCopy code

#include <iostream> #include <stack> struct Node {    int data;    Node* left;    Node* right;    Node(int val) {        data = val;        left = nullptr;        right = nullptr;    } }; // Iterative Inorder Traversal void iterativeInorder(Node* root) {    if (root == nullptr)        return;    std::stack<Node*> stk;    Node* current = root;    while (current || !stk.empty()) {        while (current) {            stk.push(current);            current = current->left;        }        current = stk.top();        stk.pop();        std::cout << current->data << " ";        current = current->right;    } } int main() {    // Create a binary tree:    //        1    //       / \    //      2   3    //     / \    //    4   5    Node* root = new Node(1);    root->left = new Node(2);    root->right = new Node(3);    root->left->left = new Node(4);    root->left->right = new Node(5);    // Perform iterative inorder traversal    std::cout << "Iterative Inorder Traversal: ";    iterativeInorder(root);    std::cout << std::endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left->left;    delete root->left->right;    delete root->left;    delete root->right;    delete root;    return 0; }

In this implementation, we use a stack to simulate the recursion of the inorder traversal. We start from the root and traverse down the left side of the tree while pushing the nodes onto the stack. Then, we pop the node from the stack, print its data, and move to its right child. The process continues until all nodes are visited.

Output:

yamlCopy code

Iterative Inorder Traversal: 4 2 5 1 3

The output shows the nodes visited in the iterative inorder traversal order: 4 -> 2 -> 5 -> 1 -> 3.