LESSON 332 OF 414 · BINARY TREES

Post Order Tree Traversal in Scala: Iterative with an Explicit Stack

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

Guided

Ctrl + Enter to check

SCALA · BINARY TREES

Post Order Tree Traversal in Scala, explained

Problem overview

The method postOrderTraversal receives the root of a binary tree and returns its values in post order as an Array[Int]: the left subtree, then the right subtree, then the node itself. This lesson solves the follow-up of the problem, which is to do it without recursion.

For the root 1 whose right child is 2, where 2 has a left child 3, the result is Array(3, 2, 1). For the root 1 with the children 2 and 3, it is Array(2, 3, 1).

Approach: simulate the recursive calls

The recursive solution relies on the call stack: each call remembers which node it is working on and what it must do next, which is go left, go right or record the value. Deep trees can overflow that stack. A loop with our own stack removes the limit, as the stack lives on the heap and can grow as large as memory allows.

Each stack entry is a pair: a node and the step its call performs next.

Step 0, LEFT_CALL: start the call for the left child.
Step 1, RIGHT_CALL: start the call for the right child.
Step 2, APPEND_TO_TRAVERSAL: record the node's value.
Any step above 2: the call is finished and has nothing left to do.

The loop pops the top entry, pushes it back with the next step, and then performs the action for the step it popped. If that action is a call for a child, the child's entry goes on top of the parent's, so it is processed first, and the parent resumes when the child is finished and gone. This is exactly the order of a recursive version, so the values come out in post order.

For the tree with root 1 and children 2 and 3, the stack goes through these states, written as (node, step) with the top at the right, and the output so far:

(1,0)
(1,1) (2,0)
(1,1) (2,1) (null,0)
(1,1) (2,1)
(1,1) (2,2) (null,0)
(1,1) (2,2)
(1,1) (2,3)                  output: 2
(1,1)
(1,2) (3,0)
...                          output: 2, 3
(1,2)
(1,3)                        output: 2, 3, 1

The entries (null, 0) are the calls on missing children. They are popped and ignored, just as a recursive call that sees null returns at once.

Step by step

Define a small class State inside Solution with two val fields, node: TreeNode and step: Int. Each instance is one simulated call.
Name the steps with three val constants, LEFT_CALL as 0, RIGHT_CALL as 1 and APPEND_TO_TRAVERSAL as 2.
Create traversal, an empty ArrayBuffer[Int], to collect the values.
Create stack, an empty ArrayBuffer[State]. The end of the buffer is the top.
Push the first call, new State(root, LEFT_CALL): it starts at the root and goes left first.
Loop while the stack is not empty.
Read the top entry into node and step using stack.last, which doesn't remove it.
Remove it with stack.remove(stack.size - 1).
Skip finished entries. Scala has no continue, so the rest of the body sits inside if (node != null && step <= APPEND_TO_TRAVERSAL). An entry that fails the test was already removed, so ignoring it lets the call beneath it resume.
Push the same node with the next step, step + 1. This must happen before a child's entry is pushed, so the parent is waiting underneath.
If the step was LEFT_CALL, push new State(node.left, LEFT_CALL).
If it was RIGHT_CALL, push new State(node.right, LEFT_CALL). Every call starts at its first step, whichever side it is on.
If it was APPEND_TO_TRAVERSAL, append node.value to traversal. Both children are done by now, which is post order.
Return traversal.toArray as the last expression.

The solution in Scala

class Solution {
    class State(val node: TreeNode, val step: Int)

    def postOrderTraversal(root: TreeNode): Array[Int] = {
        val LEFT_CALL = 0
        val RIGHT_CALL = 1
        val APPEND_TO_TRAVERSAL = 2
        val traversal = scala.collection.mutable.ArrayBuffer[Int]()
        val stack = scala.collection.mutable.ArrayBuffer[State]()
        stack += new State(root, LEFT_CALL)

        while (stack.nonEmpty) {
            val node = stack.last.node
            val step = stack.last.step
            stack.remove(stack.size - 1)

            if (node != null && step <= APPEND_TO_TRAVERSAL) {
                stack += new State(node, step + 1)

                if (step == LEFT_CALL) {
                    stack += new State(node.left, LEFT_CALL)
                } else if (step == RIGHT_CALL) {
                    stack += new State(node.right, LEFT_CALL)
                } else if (step == APPEND_TO_TRAVERSAL) {
                    traversal += node.value
                }
            }
        }

        traversal.toArray
    }
}

Scala details:

class State(val node: TreeNode, val step: Int) needs no body. The val in front of each constructor parameter turns it into a public, read-only field. Without val, stack.last.node would not compile.
new is optional in Scala 3 for classes like this one, but the lesson uses it and it is always allowed.
A buffer as a stack. += pushes at the end, last reads the end, and remove(i) deletes the element at index i, so remove(stack.size - 1) pops. stack.last on an empty buffer throws, but the loop condition rules that out.
val constants can't be reassigned, and they give the numbers 0, 1 and 2 readable names.
Pushing null nodes is allowed. A State can hold null, and the node != null test discards such entries.
The last expression, traversal.toArray, is the method's result.

Complexity

Time: O(n). Every real node produces four entries (steps 0 to 3), and every missing child produces one, so the loop runs at most about 4n + n + 1 times, each with constant work.

Space: O(h) for the stack plus O(n) for the result, where h is the height of the tree. Unlike recursion, the depth lives in a heap object: a chain of 100,000 nodes returns normally, while the recursive version of the same traversal typically ends in a StackOverflowError with the JVM's default stack size.

Edge cases and common mistakes

Empty tree. The first entry is (null, 0). It is popped, ignored, and the loop ends with an empty array.
Single node. The node goes through steps 0, 1 and 2 and its value is recorded once.
Pushing the child before the parent. If new State(node, step + 1) were pushed after the child's entry, the child would sit under its parent, and the parent would run its next step before the child was done. The order would no longer be post order.
Starting a right child at RIGHT_CALL. A call must begin with its left step, so the right child starts at LEFT_CALL.
Forgetting to remove the entry. Reading the top without removing it makes the loop run forever.
Recording the value at the wrong step. Appending at step 0 or 1 gives pre order or in order instead.

Testing

Root 1, right child 2, whose left child is 3: Array(3, 2, 1).
Root 1 with children 2 and 3: Array(2, 3, 1).
Root 1 with left child 2 (children 4, 5) and right child 3 (right child 6): Array(4, 5, 2, 6, 3, 1).
null: an empty array.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free