Daily Dose of DSA

Question Link: https://leetcode.com/problems/binary-tree-postorder-traversal/description/

Using Recursion :

It uses a helper function, postorder, to perform the traversal recursively.
The postorder function visits the left subtree, then the right subtree, and finally appends the current node's value to the result vector.
The postorderTraversal function calls the postorder function to perform the traversal and returns the resulting postorder traversal sequence as a vector.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    void postorder(TreeNode* root)
    {
        if(root==NULL) return;
        postorder(root->left);
        postorder(root->right);
        ans.push_back(root->val);

    }
    vector<int> postorderTraversal(TreeNode* root) {
        postorder(root);
        return ans;
    }
};

Using 2 Stack with Iteration :

The postorderTraversal function takes the root of the binary tree as input and returns a vector containing the postorder traversal sequence.
It uses two stacks, st1 and st2, to store the nodes during the traversal.
Initially, the root is pushed onto st1.
While st1 is not empty, the top node is popped from st1, pushed onto st2, and its left and right child (if any) are pushed onto st1.
Once all the nodes have been traversed and pushed onto st2, the nodes are popped from st2 one by one, and their values are appended to the result vector ans.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
 vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root==NULL) return ans;
        stack<TreeNode*>st1,st2;
        st1.push(root);
        while(!st1.empty())
        {
            root = st1.top();
            st1.pop();
            st2.push(root);
            if(root->left!=NULL) st1.push(root->left);
            if(root->right!=NULL) st1.push(root->right);
        }

        while(!st2.empty())
        {
            TreeNode* r = st2.top();
            ans.push_back(r->val);
            st2.pop();
        }

        return ans;
    }
};

Using 1 stack with Iteration :

The postorderTraversal function takes the root of the binary tree as input and returns a vector containing the postorder traversal sequence.
It uses a stack st to store the nodes during the traversal.
The code uses a while loop that continues until the stack is empty and the current node is NULL.
In each iteration, it checks if the current node is not NULL. If true, it pushes the current node onto the stack and moves to its left child.
If the current node is NULL, it checks the right child of the top node in the stack. If the right child exists and is not the last visited node, it updates the current node as the right child and continues the loop.
If the right child does not exist or has been visited, it means the traversal of the current subtree is complete. It pops the top node from the stack, adds its value to the result vector, and updates the last visited node.
Finally, it returns the result vector containing the postorder traversal sequence.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == NULL) return ans;

        stack<TreeNode*> st;
        TreeNode* node = root;
        TreeNode* lastVisited = NULL;

        while (!st.empty() || node != NULL) {
            if (node != NULL) {
                st.push(node);
                node = node->left;
            } else {
                TreeNode* x = st.top();

                // Check if right child exists and is not visited yet
                if (x->right != NULL && x->right != lastVisited) {
                    node = x->right;
                } 
                else {
                    ans.push_back(x->val);
                    lastVisited = x;
                    st.pop();
                }
            }
        }

        return ans;
    }
};

Daily Dose of DSA - Day 24

B.T Postorder Traversal using Recursion (TC:O(n) & SC:O(n)(call stack)) & Stack with Iteration (TC:O(n) & SC:O(2n)(2 stack)& SC: O(n)(1 stack))

Table of contents

Using Recursion :

Using 2 Stack with Iteration :

Using 1 stack with Iteration :