145. Binary Tree Postorder Traversal

Stack Tree Depth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

Postorder (left->right->root) is the reverse of a modified preorder (root->right->left). Collect root->right->left using a stack (push left before right), then reverse the result.

Algorithm

1Push root onto stack.
2While not empty: pop node, prepend to result (or push to another stack).
3Push node.left (if not null), then node.right (if not null).
4Result is root->right->left reversed -> left->right->root.

Example Walkthrough

Input: root = [1,null,2,3]

1.Pop 1->collect. Push right(2). Pop 2->collect. Push right(null), left(3). Pop 3->collect.
2.Collected (root->right->left): [1,2,3]. Reversed: [3,2,1].

Output: [3,2,1]

Common Pitfalls

•Reverse or use AddFirst - postorder is not a simple stack reversal of preorder.

145.cs

// Approach: Reverse-preorder trick for iterative postorder (left → right → root).
// Perform a modified preorder traversal (root → right → left) using a stack.
// Collect values into a list, then reverse the list at the end.
// This avoids the complexity of a true iterative postorder which requires tracking the last visited node.
// Time: O(n) Space: O(n) for the stack and result list.

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public IList<int> PostorderTraversal(TreeNode root)
    {
        List<int> result = new();
        //PostorderRecursion(root, result);
        //PostorderIterativeUsing2Stack(root, result);
        PostorderIterativeUsing1Stack(root, result);
        return result;
    }

    private void PostorderRecursion(TreeNode root, IList<int> result)
    {
        if (root == null)
            return;

        PostorderRecursion(root.left, result);
        PostorderRecursion(root.right, result);
        result.Add(root.val);
    }

    private void PostorderIterativeUsing2Stack(TreeNode root, IList<int> result)
    {
        if (root == null)
            return;

        Stack<TreeNode> st1 = new Stack<TreeNode>();
        Stack<TreeNode> st2 = new Stack<TreeNode>();
        st1.Push(root);
        while (st1.Count > 0)
        {
            TreeNode node = st1.Pop();
            if (node != null)
                st2.Push(node);

            if (node.left != null)
                st1.Push(node.left);

            if (node.right != null)
                st1.Push(node.right);
        }

        while (st2.Count > 0)
        {
            TreeNode node = st2.Pop();
            result.Add(node.val);
        }
    }

    private void PostorderIterativeUsing1Stack(TreeNode root, IList<int> result)
    {
        if (root == null)
            return;

        Stack<TreeNode> st = new Stack<TreeNode>();
        TreeNode cur = root;

        while (st.Count > 0 || cur != null)
        {
            if (cur != null)
            {
                st.Push(cur);
                cur = cur.left;
            }
            else
            {
                TreeNode temp = st.Peek().right;
                if (temp == null)
                {
                    temp = st.Pop();
                    result.Add(temp.val);
                    while (st.Count > 0 && temp == st.Peek().right)
                    {
                        temp = st.Pop();
                        result.Add(temp.val);
                    }
                }
                else
                    cur = temp;
            }
        }
    }
}

Was this solution helpful?