Start learning free

LESSON 307 OF 347 · BINARY TREES

Post Order Tree Traversal in C#: Iterative with an Explicit Stack

Practice O(n) Read the full explanation

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

STEP 1 OF 14
    Ctrl + Enter to check

    C# · BINARY TREES

    Post Order Tree Traversal in C#, explained

    Problem overview

    The method PostOrderTraversal receives the root of a binary tree and returns a List<int> with its values in post order: left subtree, right subtree, then the node itself. This lesson answers the statement's follow up and does it iteratively, with a loop and an explicit stack, without recursion.

    For the tree [1, null, 2, 3] (1 has the right child 2, and 2 has the left child 3), the answer is [3, 2, 1].

    Approach: simulate the recursive calls

    The recursive solution does three things in each call: recurse left, recurse right, record the value. The program's call stack remembers which of the three things each pending call still has to do. To remove the recursion, this lesson builds that bookkeeping by hand.

    Each entry on the stack is a State: a node plus a step number saying what that simulated call does next.

    • Step 0 (LEFT_CALL): go into the left child.
    • Step 1 (RIGHT_CALL): go into the right child.
    • Step 2 (APPEND_TO_TRAVERSAL): record the node's value.
    • Any step above 2: the call is finished.

    The loop takes the top entry off the stack and pushes it back with the step advanced by one. Then it performs the action of the step it took off. If that action is a call, it pushes a new entry for the child, starting at step 0. The child sits on top of its parent, so it runs to completion first, and the parent resumes at its next step afterwards. This is exactly how the call stack behaves in the recursive version.

    Simpler iterative solutions exist, for example a stack that produces node, right, left order and then reverses the list. The simulation is more code, but it is a general technique: it turns any recursive function into a loop, whatever it does between its calls.

    Step by step

    1. Define State inside Solution with a public TreeNode node, a public int step and a constructor that stores both. Each instance is one simulated call.
    2. Name the steps. LEFT_CALL, RIGHT_CALL and APPEND_TO_TRAVERSAL are 0, 1 and 2.
    3. Create the output list traversal.
    4. Create the stack as a Stack<State>.
    5. Push the first call: the root at step LEFT_CALL.
    6. Loop while the stack is not empty, using stack.Count > 0.
    7. Read the top with Peek() into node and step.
    8. Remove it with Pop(). It is pushed back right away, with the next step, unless the call is finished.
    9. Skip finished calls. If node is null or step is above APPEND_TO_TRAVERSAL, call continue. The entry is already off the stack, so the call below it resumes on the next iteration.
    10. Push the same call with step + 1. This must happen before pushing a child. Then, when the child is finished and popped, this call resumes at its next action.
    11. Step 0: push the left child at LEFT_CALL.
    12. Step 1: push the right child at LEFT_CALL as well, because every call starts by going left.
    13. Step 2: add node.val to traversal. Both children are finished by now, which is what post order requires.
    14. Return traversal after the loop.

    The solution in C#

    class Solution {
    class State {
        public TreeNode node;
        public int step;
        public State(TreeNode node, int step) {
            this.node = node;
            this.step = step;
        }
    };

    public List<int> PostOrderTraversal(TreeNode root) {
        int LEFT_CALL = 0;
        int RIGHT_CALL = 1;
        int APPEND_TO_TRAVERSAL = 2;
        List<int> traversal = new List<int>();
        Stack<State> stack = new Stack<State>();
        stack.Push(new State(root, LEFT_CALL));

        while (stack.Count > 0) {
            TreeNode node = stack.Peek().node;
            int step = stack.Peek().step;
            stack.Pop();

            if (node == null || step > APPEND_TO_TRAVERSAL) {
                continue;
            }

            stack.Push(new State(node, step + 1));

            if (step == LEFT_CALL) {
                stack.Push(new State(node.left, LEFT_CALL));
            } else if (step == RIGHT_CALL) {
                stack.Push(new State(node.right, LEFT_CALL));
            } else if (step == APPEND_TO_TRAVERSAL) {
                traversal.Add(node.val);
            }
        }

        return traversal;
    }
}

    C# details:

    • Nested class. State is declared inside Solution. Without an access modifier, a nested class is private, so it is only visible inside Solution, which is all this solution needs. Its fields are public so the loop can read them.
    • this.node = node. In the constructor, the parameter and the field have the same name, so this. picks the field.
    • Stack<T> comes from System.Collections.Generic. Push adds on top, Peek reads the top without removing it, Pop removes and returns it, and Count is the size. Calling Pop or Peek on an empty stack throws an InvalidOperationException, which this loop avoids by checking Count first.
    • The semicolon after a class. The closing }; of State is allowed in C#. The semicolon is optional there and changes nothing.
    • The three step values are plain local variables. They never change, so const int would also work.

    Tracing the example

    For [1, null, 2, 3], written as (node, step), the stack goes through these main stages:

    1. Start: (1, 0). Pop it, push (1, 1), then push (null, 0) for the missing left child.
    2. (null, 0) is popped and skipped. Then (1, 1) is popped: push (1, 2) and push (2, 0) for the right child.
    3. (2, 0) is popped: push (2, 1) and push (3, 0). Then (3, 0) leads to (3, 1) and (3, 2) in the same way, with two empty children skipped on the way. When (3, 2) is popped, 3 is added.
    4. (3, 3) is skipped as finished. Then (2, 1) leads to (2, 2) and 2 is added.
    5. Finally (1, 2) is popped and 1 is added, giving [3, 2, 1].

    Complexity

    Time: O(n). Each real node is pushed four times: once at each of the steps 0, 1, 2 and the finished step 3, plus the entries for missing children, of which there are at most n + 1. The total number of pushes is proportional to n.

    Space: O(h) for the stack, where h is the height of the tree, plus the output list. The stack lives on the heap, so a very deep tree does not overflow the call stack as recursion could.

    Edge cases and common mistakes

    • Empty tree. The first entry holds a null node. It is popped and skipped, the stack is empty, and an empty list comes back.
    • Pushing the parent after the child. The parent has to go back on the stack first, with the advanced step. If the child went first, the child would run after its parent instead of before it.
    • Starting children at the wrong step. A child is a new call, so it starts at LEFT_CALL, not at the parent's step.
    • Not skipping null nodes. Reading node.left on null throws a NullReferenceException.
    • Peeking without popping. If the entry is never popped, the same state would be processed again forever.
    • Appending at the wrong step. Adding the value at step 0 or 1 gives pre order or in order instead of post order.

    Testing

    • [1, null, 2, 3] gives [3, 2, 1].
    • A single node [5] gives [5].
    • An empty tree gives [].
    • The tree [1, 2, 3] gives [2, 3, 1].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free