Data Structures: How to Build an Iterator for a Binary Tree

Let’s say we already have a binary tree, and we want to build an Iterator to return the nodes in our tree in order.  If we were just listing the nodes, we could follow this recursive algorithm:

1. Go to the left child (if it exists)
2. Output the current node
3. Go to the right child (if it exists)

Consider this tree:

We would start at the root (M); we’d immediately go to the left (F), then go to the left again (A).  There are no more values to go to the left, so we’d output the current node (A).  Then we’d go to the right - but there’s nothing to the right of A.  So we’d return.  This would return us to the previous level of recursion, where we’d output the current node (F).  We’d then go to the right (K); the next step would be to go to the left (J), then go to the left again (G).  We’d then output G as there’s no further left to go to; there’s nothing to the right, so we’d return to previous level of recursion (J).  We’d output J, and so on.  Eventually we’d output the values in order:

A, F, G, J, K, L, M, Z

However, for an Iterator, we can’t “pause” our recursion so we have to simulate it instead.  This means we’ll have to use a Stack to point to identify where we are in the tree.

We have 4 methods to implement:

1. addToStack
• This adds a node to the stack, and then adds its left child to the stack, then adds that node’s left child to the stack, until there are no more left children.
2. Constructor
• Here we instantiate a stack.
• We call addToStack for the root - this adds all direct left descendants to the stack.
3. next
• We need to pop the stack - let’s call this node result.
• We need to add result’s right child and all of result’s right child’s left descendants to the stack.
• We return result’s value.
4. hasNext
• If the stack is empty, we don’t have anything left.

Consider the following tree again:


If we create a stack, and start with M and all left descendants to the stack, we end up with a stack that looks like this:

top => A => F => M

With A on the top of the stack.  If we call next() we return A.  If we call next() again, we get F as our result, but we add K, J, and G to the stack before returning F.  So our new stack looks like this:

top => G => J => K => M

We can call next() a few more times and return G and J; when we call next() again, we get K as our result, but we also add L to the stack before returning K.  So our new stack looks like this:

top => L => M

We call next() and return L, then we call next() again - we get M as our result, but we also add Z to the stack before returning M:

top => Z

We call next() one last time to return Z.