Two-Stack Postorder Traversal

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;

        stack<TreeNode*> st1, st2;
        st1.push(root);

        while (!st1.empty()) {
            TreeNode* node = st1.top();
            st1.pop();
            st2.push(node);

            if (node->left) st1.push(node->left);
            if (node->right) st1.push(node->right);
        }

        while (!st2.empty()) {
            res.push_back(st2.top()->val);
            st2.pop();
        }

        return res;
    }
};

One stack Postorder Traversal

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* curr = root;
        TreeNode* lastVisited = nullptr;

        while (curr != nullptr || !st.empty()) {
            if (curr != nullptr) {
                st.push(curr);
                curr = curr->left; // go as far left as possible
            } else {
                TreeNode* peekNode = st.top();
                // if right child exists and hasn't been visited, go right
                if (peekNode->right != nullptr && lastVisited != peekNode->right) {
                    curr = peekNode->right;
                } else {
                    res.push_back(peekNode->val); // process node
                    lastVisited = peekNode;       // mark as visited
                    st.pop();
                }
            }
        }

        return res;
    }
};

Preoder Inorder Postorder Recursive call

class Solution {
public:
    void preorderHelper(TreeNode* root, vector<int>& res) {
        if (!root) return;
        res.push_back(root->val);                // Node
        preorderHelper(root->left, res);         // Left
        preorderHelper(root->right, res);        // Right
    }

    void inorderHelper(TreeNode* root, vector<int>& res) {
        if (!root) return;
        inorderHelper(root->left, res);          // Left
        res.push_back(root->val);                // Node
        inorderHelper(root->right, res);         // Right
    }

    void postorderHelper(TreeNode* root, vector<int>& res) {
        if (!root) return;
        postorderHelper(root->left, res);        // Left
        postorderHelper(root->right, res);       // Right
        res.push_back(root->val);                // Node
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderHelper(root, res);
        return res;
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorderHelper(root, res);
        return res;
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorderHelper(root, res);
        return res;
    }
};