Iterative In-Order Traversal

19 Jan, 2020

This article presents an iterative adaptation of the In-Order Traversal (IOT) of a binary tree (an inherently recursive traversal).

Properties of IOT

IOT is said to be the most common binary tree traversal (CtCI).
the IOT printout of two different trees can be the same. For instance, consider two different BST trees with the same values, but a different arrangement of nodes. Their IOT serialization will always result in the items in sorted order (even with a placeholder value for nil items).

Recursive traversal

The recursive traversal pattern is: Left, Current, Right

iot(node):
    if node is nil:
        return
    iot(node.left)
    process(node)
    iot(node.right)

Iterative traversal

in_order(node):
    stack = [node]
    next = node.left
    while stack or next:
        if next:
            stack.append(next)
            next = next.left
        else:
            item = stack.pop()
            process(item)
            next = item.right

Understanding the iterative IOT algorithm

I believe that it's useful to develop an intuition for traversal algorithms to either commit them to memory or to be able to derive them when one forgets. The first landmark to recreate the iterative mechanics of IOT, is the condition for looping. When we visualize in-order-traversal (order being conventionally from left to right, although the same rules would apply from right to left), it's obvious that for any ancestral node N, all its left descendants must be processed before N. So it's understandable that as we traverse the tree from the root, and encounter left descendants, we must place ancestor items on a stack, for later processing.

stack = []
item = root
while item:
    stack.append(item)
    item = item.left

We assign the root node to an item variable and establish that the variable must always point to a non-nil left child as the condition to continue the traversal.

So what then? What should happen when we get to an item without a left child? Well, it means that we can now process the current item. So let's add a condition here to that effect. If the item has a left child, the item is pushed onto the stack and the child is discovered, else the item itself is processed.

stack = []
item = root
while item:
    if item.left:
        stack.append(item)
        item = item.left
    else:
        process(item)

According to IOT, after processing an item, we want to resume the discovery on its right branch, starting with its direct right child. So let's set the right child as the next item for the upcoming iteration after processing the item.

stack = []
item = root
while item:
    if item.left:
        stack.append(item)
        item = item.left
    else:
        process(item)
        item = item.right

We check that item.left is non-nil before assigning item = item.left. This ensures that the loop completely traverses the left-most branch. But not having a similar check before item = item.right risks that the loop may stop on the first empty right child, even though there might still be ancestors to process on the stack. To resolve this situation, pop an ancestor from the stack and assign it as an item to process.

stack = []
item = root
while item:
    if item.left:
        stack.append(item)
        item = item.left
    else:
        process(item)
        if item.right:
            item = item.right
        else:
            # pop an ancestor item
            item = stack.pop()

Consider the situation where an ancestor was just popped from the stack and assigned to item. The intention can only be to process it over the next iteration, not to traverse its left descendants again (as it's about to happen). How can we enforce this? We could force the processing of a just popped (ancestor) item by setting its left child to nil.

stack = []
item = root
while item:
    if item.left:
        stack.append(item)
        item = item.left
    else:
        process(item)
        if item.right:
            item = item.right
        else:
            item = stack.pop()
            item.left = nil

But this approach mutates the tree, which might sometimes be undesirable. A less destructive approach is to track whether the current item has an upcoming left child to visit, in a separate dedicated variable that we can control freely, without changing the original data structure. Let's call this new variable next and set it to the value of item.left at the onset. The algorithm thus becomes:

stack = []
item = root
next = item.left
while item:
    if next:
        stack.append(item)
        item = next
        next = item.left
    else:
        process(item)
        if item.right:
            item = item.right
            next = item.left
        else:
            item = stack.pop()
            next = nil

Observe that each time we assign an item we also assign the next one. If item has no right child to visit, its parent is popped from the stack and becomes the current item, simultaneously a nil value is given to next to prevent revisiting its left child at the next iteration. Observe, however, that prior to that next = nil line, next is already set to nil, re-setting it to nil is purely for consistency and clarity. The line can be removed, if you wish to be a bit more succinct.

stack = []
item = root
next = item.left
while item:
    if next:
        stack.append(item)
        item = next
        next = item.left
    else:
        process(item)
        if item.right:
            item = item.right
            next = item.left
        else:
            item = stack.pop()

What happens if the stack itself is already empty when we try to pop from it? Well, it means that we're done. So let's handle that case and assign nil to item, which will terminate the loop.

stack = []
item = root
next = item.left
while item:
    if next:
        stack.append(item)
        item = next
        next = item.left
    else:
        process(item)
        if item.right:
            item = item.right
            next = item.left
        else:
            if stack:
                item = stack.pop()
            else:
                item = nil

The above algorithm uses an item variable which must point to a non-nil value as a condition for its loop. But within the loop, we have to ensure that the stack is not empty before popping from it. Can the algorithm be adapted to combine those conditions instead? Yes, we can make a non-empty stack a condition for the loop, which implies that there's an item in it.

stack = [root]
next = root.left
while stack:
    ...
    ...

However, we must pay attention to how items are popped and processed from the stack. Note previously that an item was never pushed onto the stack if it did not have a left child (a next). It was processed right away. The stack was only for items that needed to be "kept aside" while their left descendants were being discovered. Now, starting with the root, we push items onto the stack and later verify whether they have a left child (a next). Thus to adapt the previous logic here, if the next is nil, then we must pop the top item from the stack for processing. Also to stay consistent with this "premature push" logic, we must push next to the stack and assign its next.left value as the next next.

stack = [root]
next = root.left
while stack:
    if next:
        stack.append(next)
        next = next.left
    else:
        item = stack.pop()
        process(item)
        ...

As we've seen previously, after processing an item we want to resume the traversal on its right branch. In this case, it's done by (prematurely) adding the right child to the stack and setting its left child as the next value.

stack = [root]
next = root.left
while stack:
    if next:
        stack.append(next)
        next = next.left
    else:
        item = stack.pop()
        process(item)
        if item.right:
            stack.append(item.right)
            next = item.right.left

In the above code, we check whether there's a right child before adding it to the stack. Then we set its left child as next. Observe though that those three steps are exactly the same as the first three lines into the loop. So we could just set next to point to the right child (whether it's nil or not) and let the upcoming iteration take care of things either way.

stack = [root]
next = root.left
while stack:
    if next:
        stack.append(next)
        next = next.left
    else:
        item = stack.pop()
        process(item)
        next = item.right

There's one final wrinkle that we must take care of. Imagine the situation where we've just popped an ancestor, discovered a right child (and assigned it to next), but the stack is now momentarily empty. Because the stack is empty, the loop will prematurely terminate, before the right child has been processed. To prevent this premature loop termination, we add as an additional, alternative condition that if next is non-nil we can also enter the loop. Thus the final version of our iterative version of IOT.

stack = [root]
next = root.left
while stack or next:
    if next:
        stack.append(next)
        next = next.left
    else:
        item = stack.pop()
        process(item)
        next = item.right

To summarize, here are a few landmarks you can anchor to to derive the above traversal yourself:

We start with the root item inserted in a stack and its left child set as the next variable.
We track both of these variables as alternative conditions to enter the loop.
The loop is divided into two branches. The first branch is the left traversal. As we discover a left descendant, we set it as the next item and add the current item to the stack, for later retrieval and processing.
The second branch is the processing of an item that has no left child to process. We pop the top item from the stack, process it, and then set the next variable to its right child.
Go back to 1.