Binary Tree Postorder Traversal — Editorial

Opening the reading…

Intuitionturning the required order into the order a stack naturally supports

Postorder means left subtree, right subtree, and root last. A stack makes the root easy to process first, but it gives you the most recently pushed child first, so directly simulating left-right-root requires extra state about whether a node has already been explored. There is a cleaner rearrangement: produce root-right-left, then reverse the completed list.

To produce root-right-left with a stack, pop a node, record its value, then push its left child before its right child. The right child is on top and is processed first; its subtree is therefore completed before the left child is popped. The sequence is root-right-left, and reversing it changes the order to left-right-root without changing which nodes were visited.

Approach

Create an empty result vector and return it immediately when root is null, because an empty tree has no node to push and no value to record.

Push root onto a stack, because every non-empty traversal needs a starting node and the stack will hold nodes whose subtrees are still waiting to be processed.

While the stack is not empty, pop its top node and append its value to result, because this constructs the forward root-right-left sequence one node at a time.

Push the left child before the right child, when those children exist, because the right child must be on top and processed before the left child.

Reverse result after the stack is empty, because the forward order is root-right-left and its exact reverse is left-right-root.

Return result after reversal, because every node was recorded once and the required postorder is now in place.

Complexitythe stack and the result each grow with the tree

MEASURE	BOUND	WHY
Time	O(n)	Each node is pushed, popped, recorded, and included in the reversal once. The stack operations are constant time per node, and reverse touches each recorded value once, so no node causes repeated traversal.
Space	O(n) extra	The output vector is O(n), but it is required output and is excluded from the extra-space bound. The working stack can contain O(n) nodes; this worst case is possible for a tree shaped so that many pending nodes accumulate, and the bound remains O(n) for every input shape.

Here n is the number of nodes in the tree.

Annotated solutionC++ · iterative · root-right-left followed by reversal

CPPThe iterative solution records root-right-left and reverses the result into postorder.

#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) {
            return result;
        }

        stack<TreeNode*> st;
        st.push(root);

        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);

            if (node->left != nullptr) {
                st.push(node->left);
            }
            if (node->right != nullptr) {
                st.push(node->right);
            }
        }

        reverse(result.begin(), result.end());
        return result;
    }
};

The two child pushes are deliberately ordered. Because a stack removes the most recently pushed item, pushing left first and right second causes the right subtree to be processed first. The final reverse is not cosmetic: it changes root-right-left into left-right-root, exactly matching the definition of postorder.

The recursive alternativeshorter code, but the runtime stack stores the traversal state

CPPThe recursive alternative follows left-right-root directly.

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        walk(root, result);
        return result;
    }

private:
    void walk(TreeNode* node, vector<int>& result) {
        if (node == nullptr) {
            return;
        }

        walk(node->left, result);
        walk(node->right, result);
        result.push_back(node->val);
    }
};

This version is a different arrangement, not an asymptotic optimisation. Its control flow mirrors the definition exactly: finish the left subtree, finish the right subtree, then record the node. The runtime call stack stores the unfinished ancestors, while the iterative version stores pending nodes explicitly in st. Both take O(n) time and O(n) extra space in the worst case; choose recursion for clarity and the explicit stack when you want direct control over memory.