LESSON 333 OF 414 · BINARY TREES

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

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

Example:

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

Output: [3,2,1]

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

STEP 1 OF 13

Guided

Ctrl + Enter to check

RUST · BINARY TREES

Post Order Tree Traversal in Rust, explained

Problem overview

The function post_order_traversal receives the root of a binary tree, as an Option<Box<TreeNode>>, and returns the node values in post order: the left subtree, then the right subtree, then the node itself. Each TreeNode has a val and two children, left and right, of the same optional boxed type.

For the tree with root 1, no left child, and a right child 2 that has a left child 3, the answer is [3, 2, 1]. The follow-up in the statement asks for an iterative solution, and this lesson solves it without any recursion.

Approach: simulate the recursive calls on your own stack

The recursive solution is three lines per node: go left, go right, record the value. When it runs, the machine keeps a call stack, and each call remembers where it is. To remove the recursion, keep that stack yourself.

Every entry on the stack stands for one call and pairs a node with a step, the next thing that call must do:

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

Each loop iteration looks at the entry on top. If the entry is finished, or its node is missing (None), it is popped, and the call underneath resumes. Otherwise the step on top is advanced by one first, and then the action for the old step is carried out. Advancing first matters: when a child's entry is pushed on top, the parent is already set to its next step, so the parent continues from the right place after the child is popped.

This is a direct translation of the recursion, so the order of recorded values is exactly post order. The stack never holds more than one entry per level of the tree plus the entry for a missing child, so it is as deep as the tree is tall.

Here is the stack before each iteration for the tree with root 1 and a single left child 2, written as (value, step), with - for a missing node and the top of the stack on the right:

(1,0)
(1,1) (2,0)
(1,1) (2,1) (-,0)
(1,1) (2,1)
(1,1) (2,2) (-,0)
(1,1) (2,2)
(1,1) (2,3)
(1,1)
(1,2) (-,0)
(1,2)
(1,3)

The line (1,1) (2,2) is the moment the entry for 2 is on top at step 2, so 2 is recorded. Then the line (1,2) records 1, giving [2, 1].

Step by step

Name the steps with three i32 constants: LEFT_CALL = 0, RIGHT_CALL = 1 and APPEND_TO_TRAVERSAL = 2. A const must state its type, and it can be declared inside the function.
Create the output traversal, an empty mutable Vec<i32>.
Create the stack as a mutable Vec<(Option<&TreeNode>, i32)>. Its entries borrow nodes instead of owning them, so the tree stays where it is. The node part is an Option because entries are also pushed for missing children.
Push the first entry: root.as_deref() paired with LEFT_CALL. The traversal starts at the root, and every call begins by going left.
Loop while the stack is not empty.
Read the top entry without removing it, as let (node, step) = *stack.last().unwrap();.
Pop finished entries. If node.is_none() or step > APPEND_TO_TRAVERSAL, call stack.pop() and continue.
Advance the step on the top entry: *stack.last_mut().unwrap() = (node, step + 1);.
Unwrap the node into a plain &TreeNode, shadowing the old name. The check in step 7 has ruled out None.
Left: if step == LEFT_CALL, push (node.left.as_deref(), LEFT_CALL).
Right: otherwise, if step == RIGHT_CALL, push (node.right.as_deref(), LEFT_CALL). A child call also starts by going left.
Record: otherwise, if step == APPEND_TO_TRAVERSAL, push node.val onto traversal. Both children have finished by now.
Return traversal after the loop.

The solution in Rust

impl Solution {
    fn post_order_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {
        const LEFT_CALL: i32 = 0;
        const RIGHT_CALL: i32 = 1;
        const APPEND_TO_TRAVERSAL: i32 = 2;
        let mut traversal: Vec<i32> = Vec::new();
        let mut stack: Vec<(Option<&TreeNode>, i32)> = Vec::new();
        stack.push((root.as_deref(), LEFT_CALL));
        while !stack.is_empty() {
            let (node, step) = *stack.last().unwrap();
            if node.is_none() || step > APPEND_TO_TRAVERSAL {
                stack.pop();
                continue;
            }
            *stack.last_mut().unwrap() = (node, step + 1);
            let node = node.unwrap();
            if step == LEFT_CALL {
                stack.push((node.left.as_deref(), LEFT_CALL));
            } else if step == RIGHT_CALL {
                stack.push((node.right.as_deref(), LEFT_CALL));
            } else if step == APPEND_TO_TRAVERSAL {
                traversal.push(node.val);
            }
        }
        traversal
    }
}

Rust details that matter here:

as_deref(). On an Option<Box<TreeNode>> it gives an Option<&TreeNode> that borrows the node inside the box, without moving anything out of it. The stack holds these references, and the tree must outlive them. It does, because root lives until the end of the function.
Copying the top entry. *stack.last().unwrap() copies the tuple out of the vector. That works because an Option<&TreeNode> and an i32 are both Copy. The borrow of the stack ends right away, so the next lines can pop or modify it.
last().unwrap() is safe because the loop runs only while the stack is not empty.
Replacing an entry. *stack.last_mut().unwrap() = (node, step + 1) assigns a whole new tuple through the mutable reference, which overwrites the old entry in place.
Shadowing. let node = node.unwrap(); reuses the name for the unwrapped reference. The earlier Option is no longer needed after the is_none() check, and unwrap() cannot panic here.
Plain if / else if on constants. The branches compare step with the named constants. Rust's match on constants would work too, but the chain keeps the three actions easy to read.

Complexity

Time: O(n). Each real node is on the stack for four iterations: three that advance it from step 0 to step 3, and a final one that pops it. Each missing child is on the stack for one iteration, and there are at most n + 1 of them. So the loop runs at most about 5n + 1 times, each with constant work.

Space: O(h) for the stack, plus the O(n) output. The stack holds one entry per node on the path from the root to the current node, and possibly one entry for a missing child. Here h is the height of the tree. Unlike the recursive solution, this depth lives on the heap in a Vec, so the traversal itself doesn't consume call-stack space in proportion to the tree's height.

Edge cases and common mistakes

Empty tree. The first entry is (None, LEFT_CALL). The first iteration pops it, and the function returns [].
Advancing the step after pushing the child. If the step is changed after the child's entry is pushed, last_mut() would point at the child's entry, not the parent's, and the traversal would go wrong. That is why the step is advanced before any push.
Not advancing at all. The same node would take the same action again and again, and the loop would never end.
Starting a child at the wrong step. A new child entry starts at LEFT_CALL, for both left and right children. Starting the right child at RIGHT_CALL would skip the child's left subtree.
Forgetting the None check. Calling unwrap() on a missing node's entry would panic.
Recording too early. The value is pushed only at step 2, after both children are finished. Recording at step 0 would give pre order.

Testing

Root 1, right child 2, and 2's left child 3: [3, 2, 1].
Root 1, children 2 and 3, 2's children 4 and 5: [4, 5, 2, 3, 1].
Root 1 with only a left child 2: [2, 1].
An empty tree: [].

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

Start learning free