Start learning free

LESSON 308 OF 348 · BINARY TREES

Post Order Tree Traversal in Kotlin: 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

    KOTLIN · BINARY TREES

    Post Order Tree Traversal in Kotlin, explained

    Problem overview

    The function postOrderTraversal takes the root of a binary tree, a TreeNode? that is null for an empty tree, and returns its values in post order as a List<Int>. Post order lists the left subtree, then the right subtree, then the node itself. For the tree [1, null, 2, 3], where 1 has a right child 2 and 2 has a left child 3, the answer is [3, 2, 1].

    The statement's follow-up asks for a solution that doesn't use recursion. A recursive solution is a few lines, but it keeps its state on the call stack, and a very deep tree can overflow it. Here the goal is to do the same traversal with a loop and a stack of your own.

    Approach: simulate the recursive calls

    Think about what one recursive call does for a node. It performs three actions in order: call itself on the left child, call itself on the right child, then record the node's value. A call that is paused after the first action must later resume at the second, and so on. The call stack exists to remember where each paused call has to resume.

    The iterative version stores that information itself. Each stack entry is a State: a node plus a step that says which action is next.

    • 0: go left, that is, start a call for the left child.
    • 1: go right.
    • 2: record the value.
    • Anything above 2: the call is finished.

    The loop takes the top entry off the stack. If it is finished, or the node is null, it is dropped, and the entry below it, the caller, becomes the top and resumes. Otherwise the loop pushes the same node back with the step increased by one, so the call remembers its place, then performs the action for the step it just read. Going left or right pushes a new entry for the child, starting at step 0, and that entry ends up on top, so it runs before the paused parent. This mirrors the call stack exactly.

    Here is the traversal of the tree [1, 2, 3] (1 with left child 2 and right child 3). Each line shows the stack from bottom to top as (node, step) after the loop handled the top entry:

    (1,0) taken        (1,1) (2,0)
(2,0) taken        (1,1) (2,1) (null,0)
(null,0) dropped   (1,1) (2,1)
(2,1) taken        (1,1) (2,2) (null,0)
(null,0) dropped   (1,1) (2,2)
(2,2) taken        (1,1) (2,3)           adds 2
(2,3) dropped      (1,1)
(1,1) taken        (1,2) (3,0)
(3,0) taken        (1,2) (3,1) (null,0)
(null,0) dropped   (1,2) (3,1)
(3,1) taken        (1,2) (3,2) (null,0)
(null,0) dropped   (1,2) (3,2)
(3,2) taken        (1,2) (3,3)           adds 3
(3,3) dropped      (1,2)
(1,2) taken        (1,3)                 adds 1
(1,3) dropped      (empty)

    The values were added in the order 2, 3, 1, which is post order for that tree.

    Step by step

    1. Define State inside Solution: a class whose primary constructor declares two val properties, node: TreeNode? and step: Int. The node is nullable because entries are pushed for missing children as well.
    2. Name the three steps. LEFT_CALL, RIGHT_CALL and APPEND_TO_TRAVERSAL are 0, 1 and 2. Names make the loop readable.
    3. Create the output list as a mutable list of Int.
    4. Create the stack as an ArrayDeque<State>. The end of the deque is the top.
    5. Push the first entry, the root at step LEFT_CALL. The traversal starts there and the first action is to go left.
    6. Loop while the stack is not empty.
    7. Read the top entry into node and step.
    8. Pop it. If the call isn't finished, it will be pushed back in a moment with its next step.
    9. Skip finished entries. A null node or a step above APPEND_TO_TRAVERSAL needs nothing more, so continue to the next iteration.
    10. Push the same node with step + 1. This must happen before a child is pushed, so that the parent is waiting underneath the child.
    11. If the step is LEFT_CALL, push the left child at step LEFT_CALL.
    12. Otherwise, if it is RIGHT_CALL, push the right child, also at LEFT_CALL, because every new call starts by going left.
    13. Otherwise, if it is APPEND_TO_TRAVERSAL, add the node's value. Both subtrees are already finished by now.
    14. Return the list after the loop, when the stack is empty.

    The solution in Kotlin

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

    fun postOrderTraversal(root: TreeNode?): List<Int> {
        val LEFT_CALL = 0
        val RIGHT_CALL = 1
        val APPEND_TO_TRAVERSAL = 2
        val traversal = mutableListOf<Int>()
        val stack = ArrayDeque<State>()
        stack.addLast(State(root, LEFT_CALL))

        while (stack.isNotEmpty()) {
            val node = stack.last().node
            val step = stack.last().step
            stack.removeLast()

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

            stack.addLast(State(node, step + 1))

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

        return traversal
    }
}

    The Kotlin details worth knowing:

    • A constructor that declares properties. class State(val node: TreeNode?, val step: Int) creates the constructor, the two properties and their getters in one line. No class body is needed.
    • Nested class. A class declared inside another class is a plain nested class, not tied to a Solution object. Code creates it with State(...) inside Solution, and from outside it would be Solution.State.
    • ArrayDeque. Kotlin has its own ArrayDeque in the standard library, so no import is needed. It offers addLast, last(), removeLast() and isNotEmpty(), which is all a stack needs. last() only reads the top, while removeLast() takes it off.
    • Smart cast. node is a local val. After node == null || ... continue, the compiler knows node is not null below that line, so node.left and node.value compile without ?..
    • Local constants. The three names are ordinary local vals. The const val form is only allowed at the top level or inside an object, so a local val is the right choice here.
    • continue in a while loop. It jumps to the next check of the condition and skips the rest of the body.

    Complexity

    Let n be the number of nodes and h the height of the tree.

    Time: O(n). Each node is handled in four loop iterations at most: one for each of its three actions and one when the finished entry is dropped. Each missing child adds one entry that is dropped at once. All the operations on the deque take constant time.

    Space: O(h) for the stack, plus the O(n) result. The stack holds the path from the root to the current node and a few more entries. Unlike the recursive version, the depth is limited by heap memory instead of the call stack, so a long chain of nodes causes no stack overflow.

    Edge cases and common mistakes

    • Empty tree. The stack starts with State(null, LEFT_CALL). The first iteration drops it and the loop ends with an empty list.
    • Pushing the parent after the child. If the incremented entry for the node were pushed after the child, the child would be underneath and run after the parent, which breaks the order.
    • Forgetting to advance the step. Pushing the node back with the same step repeats the same action forever.
    • Starting child entries at the wrong step. A child's call must start at LEFT_CALL whether it was reached from the left or from the right.
    • Reading the top and forgetting to pop. last() doesn't remove the entry. Without the removeLast(), the same entry would be read again and again.
    • Treating null children as errors. Entries for missing children are pushed on purpose and dropped by the first check in the loop, which keeps the push code free of null tests.

    Testing

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