Lecture 285:- Iterative Preorder

Here's a C++ implementation of iterative preorder 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 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 << " ";        // Push right child first so that left child is processed first during next iteration        if (current->right)            stk.push(current->right);        if (current->left)            stk.push(current->left);    } } 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;    // 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 preorder traversal. We start with the root node and push it onto the stack. Then, in the while loop, we pop the top node from the stack, print its data, and push its right and left children onto the stack (if they exist). The right child is pushed first so that the left child will be processed first in the next iteration, ensuring the correct order of preorder traversal.

Output:

yamlCopy code

Iterative Preorder Traversal: 1 2 4 5 3

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