Lecture 277:- Binary Tree Traversal Easy Method 2

Another easy method to perform binary tree traversal is using an iterative approach with the help of a stack data structure. This method avoids the use of recursion and can be useful to handle large binary trees without causing stack overflow. Here's a simple implementation in C++ for each type of traversal (inorder, preorder, and postorder):

cppCopy code

#include <iostream> #include <stack> struct Node {    int data;    Node* left;    Node* right;    Node(int val) {        data = val;        left = nullptr;        right = nullptr;    } }; // Inorder Traversal: Left -> Root -> Right void inorderTraversal(Node* root) {    std::stack<Node*> s;    Node* curr = root;    while (curr || !s.empty()) {        while (curr) {            s.push(curr);            curr = curr->left;        }        curr = s.top();        s.pop();        std::cout << curr->data << " ";        curr = curr->right;    } } // Preorder Traversal: Root -> Left -> Right void preorderTraversal(Node* root) {    std::stack<Node*> s;    if (root) s.push(root);    while (!s.empty()) {        Node* curr = s.top();        s.pop();        std::cout << curr->data << " ";        if (curr->right) s.push(curr->right);        if (curr->left) s.push(curr->left);    } } // Postorder Traversal: Left -> Right -> Root void postorderTraversal(Node* root) {    std::stack<Node*> s1, s2;    if (root) s1.push(root);    while (!s1.empty()) {        Node* curr = s1.top();        s1.pop();        s2.push(curr);        if (curr->left) s1.push(curr->left);        if (curr->right) s1.push(curr->right);    }    while (!s2.empty()) {        Node* curr = s2.top();        s2.pop();        std::cout << curr->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 different traversals    std::cout << "Inorder Traversal: ";    inorderTraversal(root);    std::cout << std::endl;    std::cout << "Preorder Traversal: ";    preorderTraversal(root);    std::cout << std::endl;    std::cout << "Postorder Traversal: ";    postorderTraversal(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 keep track of nodes during traversal. For inorder traversal, we keep traversing left until reaching the leftmost node, and then we backtrack and visit the right subtree. For preorder traversal, we visit nodes while pushing their right and left children onto the stack. For postorder traversal, we use two stacks to reverse the output order of the right-root-left traversal.

The iterative approach provides an alternative to recursion, making the traversal efficient and allowing it to handle large binary trees without causing stack overflow.