This is the third article in a series on converting recursive algorithms into iterative algorithms. If any of what follows seems confusing, you may want to read the earlier articles first.

This is an extra article that I hadn’t planned. I’m writing it because in a comment on the previous article a reader asked me to show a less mathematical example and suggested tree traversal. So that’s the subject of this article: We’ll take a binary tree and flatten it into a list, first recursively, then iteratively.

### The challenge

First, let’s define a binary tree to be either empty or given by a node having three parts: (1) a value, (2) a left subtree, and (3) a right subtree, where both of the subtrees are themselves binary trees. In Haskell, we might define it like so:

`data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a)`

In Python, which we’ll use for the rest of this article, we’ll say that `None`

represents an empty tree and that the following class represents a node:

```
import collections
= collections.namedtuple('Node', 'val left right')
Node
# some sample trees having various node counts
= None # empty tree
tree0 = Node(5, None, None)
tree1 = Node(7, tree1, None)
tree2 = Node(7, tree1, Node(9, None, None))
tree3 = Node(2, None, tree3)
tree4 = Node(2, Node(1, None, None), tree3) tree5
```

Let us now define a function to flatten a tree using an in-order traversal. The recursive definition is absurdly simple, the data type having only two cases to consider:

```
def flatten(bst):
# empty case
if bst is None:
return []
# node case
return flatten(bst.left) + [bst.val] + flatten(bst.right)
```

A few tests to check that it does what we expect:

```
def check_flattener(f):
assert f(tree0) == []
assert f(tree1) == [5]
assert f(tree2) == [5, 7]
assert f(tree3) == [5, 7, 9]
assert f(tree4) == [2, 5, 7, 9]
assert f(tree5) == [1, 2, 5, 7, 9]
print 'ok'
# ok check_flattener(flatten)
```

Our challenge for today is to convert `flatten`

into an iterative version.
Other than a new trick – partial evaluation – the transformation is straightforward, so I’ll move quickly.

Let’s do this!

### Eliminating the first recursive call

First, let’s separate the base case from the incremental work:

```
def step(bst):
return flatten(bst.left) + [bst.val] + flatten(bst.right)
def flatten(bst):
if bst is None:
return []
return step(bst)
```

And let’s break the incremental work into smaller pieces to see what’s going on.

```
def step(bst):
= flatten(bst.left)
left
left.append(bst.val)= flatten(bst.right)
right
left.extend(right)return left
def flatten(bst):
if bst is None:
return []
return step(bst)
```

Let’s try to get rid of the first recursive call by assuming that somebody has passed us its result via a secret argument `left`

:

```
def step(bst, left=None):
if left is None:
= flatten(bst.left)
left
left.append(bst.val)= flatten(bst.right)
right
left.extend(right)return left
def flatten(bst):
if bst is None:
return []
return step(bst)
```

And now we’ll make `step`

return values that parallel its input arguments:

```
def step(bst, left=None):
if left is None:
= flatten(bst.left)
left
left.append(bst.val)= flatten(bst.right)
right
left.extend(right)return bst, left # <-- add bst
def flatten(bst):
if bst is None:
return []
return step(bst)[-1] # <-- note [-1]
```

In the first recursive call, the transformation applied to `bst`

is `.left`

, so we want to apply the opposite transformation to `bst`

in the returned values.
And what’s the opposite of descending to a node’s left subtree?
It’s ascending to the node’s parent.
So we want something like this:

```
# this code does not work!
def step(bst, left=None):
if left is None:
= flatten(bst.left)
left
left.append(bst.val)= flatten(bst.right)
right
left.extend(right)return get_parent(bst), left # <-- need get_parent
```

But we’re stuck.
We can’t define `get_parent`

because our tree data structure doesn’t keep track of parents, only children.

New plan:
Maybe we can assume that someone has *passed us* the node’s parent and go from there?

But this plan hits the same brick wall:
If we add a new argument to accept the parent, we must for parallelism add a new return value to emit the transformed parent, which is the parent of the parent.
But we can’t compute the parent of the parent because, as before, we have no way of implementing `get_parent`

.

So we do what mathematicians do when their assumptions hit a brick wall: we strengthen our assumption!
Now we assume that someone has passed us *all of the parents*, right up to the tree’s root.
And that assumption gives us what we need:

```
def step(bst, parents, left=None):
if left is None:
= flatten(bst.left)
left
left.append(bst.val)= flatten(bst.right)
right
left.extend(right)return parents[-1], parents[:-1], left
```

Note that we’re using the Python stack convention for `parents`

; thus the immediate parent of `bst`

is given by the final element `parents[-1]`

.

As a simplification, we can eliminate the `bst`

argument by considering it the final parent pushed onto the stack:

```
def step(parents, left=None):
= parents.pop() # <-- bst = top of parents stack
bst if left is None:
= flatten(bst.left)
left
left.append(bst.val)= flatten(bst.right)
right
left.extend(right)return parents, left
```

Now that `step`

requires the `parents`

stack as an argument, the base function must provide it:

```
def flatten(bst):
if bst is None:
return []
= [bst]
parents return step(parents)[-1]
```

But we still haven’t eliminated the first recursive call.
To do that, we’ll need to pass the `step`

function a value for its `left`

argument, which will cause the recursive call to be skipped.

But we only know what that value should be for one case, the base case, when `bst`

is `None`

; then `left`

must be `[]`

.
To get to that case from the tree’s root, where `bst`

is definitely not `None`

, we must iteratively replicate the normal recursive calls on `bst.left`

until we hit the leftmost leaf node.
And then, to compute the desired result, we must reverse the trip, iterating the `step`

function until we have returned to the tree’s root, where the `parents`

stack must be empty:

```
def flatten(bst):
# find initial conditions for secret-feature "left"
= []
left = []
parents while bst is not None:
parents.append(bst)= bst.left
bst # iterate to compute the result
while parents:
= step(parents, left)
parents, left return left
```

And just like that, one of the recursive calls has been transformed into iteration. We’re halfway to the finish line!

### Eliminating the second recursive call

But we still have to eliminate that final recursive call to `flatten`

, now sequestered in `step`

.
Let’s take a closer look at that function after we make its `left`

argument required since it always gets called with a value now:

```
def step(parents, left):
= parents.pop()
bst
left.append(bst.val)= flatten(bst.right)
right
left.extend(right)return parents, left
```

To get rid of the recursive call to `flatten`

, we’re going to use a new trick: partial evaluation.
Basically, we’re going to replace the call to `flatten`

with the function body of `flatten`

, after we rename all its variables to prevent conflicts.
So let’s make a copy of `flatten`

and suffix all its variables with `1`

:

```
def flatten1(bst1):
= []
left1 = []
parents1 while bst1 is not None:
parents1.append(bst1)= bst1.left
bst1 while parents1:
= step(parents1, left1)
parents1, left1 return left1
```

And then let’s make its arguments and return values explicit:

```
= ARGUMENTS
(bst1, ) = []
left1 = []
parents1 while bst1 is not None:
parents1.append(bst1)= bst1.left
bst1 while parents1:
= step(parents1, left1)
parents1, left1 = (left1, ) RETURNS
```

And then we’ll drop this expansion into `step`

:

```
def step(parents, left):
= parents.pop()
bst
left.append(bst.val)# -- begin partial evaluation --
= (bst.right, )
(bst1, ) = []
left1 = []
parents1 while bst1 is not None:
parents1.append(bst1)= bst1.left
bst1 while parents1:
= step(parents1, left1)
parents1, left1 = (left1, )
(right, ) # -- end partial evaluation --
left.extend(right)return parents, left
```

Now we can eliminate code by fusion across the partial-evaluation boundary.

First up: `left1`

.
We can now see that this variable accumulates values that, in the end, get appended to `left`

(via the return variable `right`

).
But we can just as well append those values to `left`

directly, eliminating `left1`

within the boundary and the call to `left.extend(right)`

without:

```
def step(parents, left):
= parents.pop()
bst
left.append(bst.val)# -- begin partial evaluation --
= (bst.right, )
(bst1, ) # left1 = [] # <-- eliminate and use left instead
= []
parents1 while bst1 is not None:
parents1.append(bst1)= bst1.left
bst1 while parents1:
= step(parents1, left)
parents1, left # (right, ) = (left, ) # <-- eliminated
# -- end partial evaluation --
# left.extend(right) # <-- eliminated
return parents, left
```

For this next fusion, we’re going to need to recall our base function to get the necessary outside scope:

```
def step(parents, left):
= parents.pop()
bst
left.append(bst.val)# -- begin partial evaluation --
= (bst.right, )
(bst1, ) = []
parents1 while bst1 is not None:
parents1.append(bst1)= bst1.left
bst1 while parents1:
= step(parents1, left)
parents1, left # -- end partial evaluation --
return parents, left
def flatten(bst):
= []
left = []
parents while bst is not None:
parents.append(bst)= bst.left
bst while parents:
= step(parents, left)
parents, left return left
```

When `flatten`

calls `step`

and the code within the partially evaluated region executes, it builds up a stack of nodes `parents1`

and then calls `step`

iteratively to pop values off of that stack and process them.
When it’s finished, control returns to `step`

proper, which then returns to its caller, `flatten`

, with the values (`parents`

, `left`

).
But look at what `flatten`

then does with `parents`

: it calls `step`

iteratively to pop values off of that stack and process them in exactly the same way.

So we can eliminate the `while`

loop in `step`

– and the recursive call! – by returning not `parents`

but `parents + parents1`

, which will make the `while`

loop in `flatten`

do the exact same work.

```
def step(parents, left):
= parents.pop()
bst
left.append(bst.val)# -- begin partial evaluation --
= (bst.right, )
(bst1, ) = []
parents1 while bst1 is not None:
parents1.append(bst1)= bst1.left
bst1 # while parents1: # <-- eliminated
# parents1, left = step(parents1, left) #
# -- end partial evaluation --
return parents + parents1, left # parents -> parents + parents1
```

And then we can eliminate `parents1`

completely by taking the values we would have appended to it and appending them directly to `parents`

:

```
def step(parents, left):
= parents.pop()
bst
left.append(bst.val)# -- begin partial evaluation --
= (bst.right, )
(bst1, ) # parents1 = [] # <-- eliminated
while bst1 is not None:
# parents1 -> parents
parents.append(bst1) = bst1.left
bst1 # -- end partial evaluation --
return parents, left # parents + parents1 -> parents
```

And now, once we remove our partial-evaluation scaffolding, our `step`

function is looking simple again:

```
def step(parents, left):
= parents.pop()
bst
left.append(bst.val)= bst.right
bst1 while bst1 is not None:
parents.append(bst1)= bst1.left
bst1 return parents, left
```

For the final leg of our journey – simplification – let’s inline the `step`

logic back into the base function:

```
def flatten(bst):
= []
left = []
parents while bst is not None:
parents.append(bst)= bst.left
bst while parents:
= parents, left
parents, left = parents.pop()
bst
left.append(bst.val)= bst.right
bst1 while bst1 is not None:
parents.append(bst1)= bst1.left
bst1 = parents, left
parents, left return left
```

Let’s eliminate the trivial argument-binding and return-value assignments:

```
def flatten(bst):
= []
left = []
parents while bst is not None:
parents.append(bst)= bst.left
bst while parents:
# parents, left = parents, left # = no-op
= parents.pop()
bst
left.append(bst.val)= bst.right
bst1 while bst1 is not None:
parents.append(bst1)= bst1.left
bst1 # parents, left = parents, left # = no-op
return left
```

And, finally, factor out the duplicated `while`

loop into a local function:

```
def flatten(bst):
= []
left = []
parents def descend_left(bst):
while bst is not None:
parents.append(bst)= bst.left
bst
descend_left(bst)while parents:
= parents.pop()
bst
left.append(bst.val)
descend_left(bst.right)return left
```

And that’s it! We now have a tight, efficient, and iterative version of our original function. Further, the code is close to idiomatic.

That’s it for this time. If you have any questions or comments, just hit me at @tmoertel or use the comment form below.

Thanks for reading!