31. DSA with C++ - Postorder with recursion and Postorder Without Recursion

Algorithm:

1. If the current node is null, return.
2. Recursively traverse the le subtree.
3. Recursively traverse the right subtree.
4. Process the current node (e.g., print its value).

Postorder with Recursion

Binary Tree in C++

 
#include <iostream>

// Binary Tree Node
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to insert a node in a binary tree
Node* insertNode(Node* root, int value) {
    if (root == nullptr) {
        return new Node(value);
    } else {
        if (value <= root->data) {
            root->left = insertNode(root->left, value);
        } else {
            root->right = insertNode(root->right, value);
        }
        return root;
    }
}

// Function to perform postorder traversal of a binary tree
void postorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }

    // Traverse the left subtree
    postorderTraversal(root->left);

    // Traverse the right subtree
    postorderTraversal(root->right);

    // Process the current node
    std::cout << root->data << " ";
}

int main() {
    Node* root = nullptr;

    // Insert nodes in the binary tree
    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 70);
    insertNode(root, 60);
    insertNode(root, 80);

    // Perform postorder traversal
    std::cout << "Postorder Traversal: ";
    postorderTraversal(root);  // Output: 20 40 30 60 80 70 50
    std::cout << std::endl;

    return 0;
}
            

Explanation
• In this implementaon, we have a Node structure that represents a node in the binary tree. Each node contains an integer data value and pointers to the le and right child nodes.
• The insertNode funcon is used to insert a new node into the binary tree. If the tree is empty, a new root node is created. Otherwise, the funcon recursively traverses the tree to f ind the appropriate posion to insert the new node.
• The postorderTraversal funcon performs the postorder traversal of the binary tree. It first recursively traverses the le subtree, then the right subtree, and finally processes the current node. In this example, we print the data value of each node during the traversal.
• In the main funcon, we create a binary tree by inserng nodes with various values. Then, we perform the postorder traversal and print the resul ng order of nodes.

Output: Postorder Traversal: 20 40 30 60 80 70 50

Algorithm

1. Create two stacks, s1 and s2.
2. Push the root node onto s1.
3. While s1 is not empty, repeat steps 4-8.
4. Pop a node curr from s1 and push it onto s2.
5. Push curr->le onto s1 if it exists.
6. Push curr ->right onto s1 if it exists.
7. Repeat steps 4-6 unl all nodes have been processed.
8. While s2 is not empty, pop a node curr from s2 and print its data.

Without Recursion

Binary Tree in C++

 
#include <iostream>
#include <stack>

// Node structure for the binary tree
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// Function to insert a node into the binary tree
void insertNode(Node*& root, int value) {
    if (root == nullptr) {
        root = new Node(value);
        return;
    }

    std::queue q;
    q.push(root);

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();

        if (curr->left == nullptr) {
            curr->left = new Node(value);
            return;
        } else {
            q.push(curr->left);
        }

        if (curr->right == nullptr) {
            curr->right = new Node(value);
            return;
        } else {
            q.push(curr->right);
        }
    }
}

// Function to perform postorder traversal of the binary tree (iterative approach)
void postorderTraversal(Node* root) {
    if (root == nullptr)
        return;

    std::stack<Node*> s1, s2;
    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() {
    Node* root = nullptr;
    insertNode(root, 1);
    insertNode(root, 2);
    insertNode(root, 3);
    insertNode(root, 4);
    insertNode(root, 5);

    std::cout << "Postorder Traversal: ";
    postorderTraversal(root); // Output: 4 5 2 3 1
    std::cout << std::endl;

    // Clean up memory (optional)
    // ...

    return 0;
}
            

• In this implementaon, we have a Node structure that represents a node in the binary tree. Each node contains an integer data value, as well as pointers to its le child and right child.
• The insertNode funcon is used to insert a new node into the binary tree. It traverses the tree using a queue to find the appropriate posion for inseron.
• The postorderTraversal funcon performs the postorder traversal of the binary tree using an iterave approach with two stacks. It simulates the postorder traversal by using two stacks: s1 for processing the nodes and s2 for storing the postorder traversal sequence.
• In the main funcon, we create a binary tree by inserng nodes with values 1, 2, 3, 4, and 5. We then perform the postorder traversal and print the data of each node.

Output: Postorder Traversal: 4 5 2 3 1