Lecture 287:- Let's Code Iterative Traversals

Here's the C++ implementation of iterative preorder, inorder, and postorder traversals for a binary tree using stacks:

cppCopy code

#include <iostream> #include <stack> struct Node {    int data;    Node* left;    Node* right;    Node(int val) {        data = val;        left = nullptr;        right = nullptr;    } }; // Iterative Preorder Traversal void iterativePreorder(Node* root) {    if (root == nullptr)        return;    std::stack<Node*> stk;    stk.push(root);    while (!stk.empty()) {        Node* current = stk.top();        stk.pop();        std::cout << current->data << " ";        if (current->right)            stk.push(current->right);        if (current->left)            stk.push(current->left);    } } // 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;    } } // Iterative Postorder Traversal void iterativePostorder(Node* root) {    if (root == nullptr)        return;    std::stack<Node*> stk1, stk2;    stk1.push(root);    while (!stk1.empty()) {        Node* current = stk1.top();        stk1.pop();        stk2.push(current);        if (current->left)            stk1.push(current->left);        if (current->right)            stk1.push(current->right);    }    while (!stk2.empty()) {        Node* current = stk2.top();        stk2.pop();        std::cout << current->data << " ";    } } 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 preorder traversal    std::cout << "Iterative Preorder Traversal: ";    iterativePreorder(root);    std::cout << std::endl;    // Perform iterative inorder traversal    std::cout << "Iterative Inorder Traversal: ";    iterativeInorder(root);    std::cout << std::endl;    // Perform iterative postorder traversal    std::cout << "Iterative Postorder Traversal: ";    iterativePostorder(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; }

Output:

yamlCopy code

Iterative Preorder Traversal: 1 2 4 5 3 Iterative Inorder Traversal: 4 2 5 1 3 Iterative Postorder Traversal: 4 5 2 3 1

The output shows the nodes visited in the iterative preorder, inorder, and postorder traversal orders respectively.