It may be more common to want to walk a binary tree in sorted order (left to right) as opposed to top to bottom as most common use case for binary trees are around sorted collections. Generally speaking any algorithm that is implemented in recursion can be converted into recursion free algorithm that makes use of stack where stack typically will contain same arguments that are normally passed to function.
Let's start from analysing and understanding what exactly happens in recursive algorithm:
def walk(node):
# 1. push all left most items on queue, the last item on queue will be the smallest
if(node.left)
walk(node.left)
# 2. print current item - since this is last on stack and we
# built stack by pushing left most items first, item being
# printed is guaranteed to always be smallest of those that have not
# yet been visited
print(node.key)
# 3. repeat step 1. and step 2. with node.right
if(node.right)
walk(node.right)
let's see what happens if we apply this algorithm on tree
D
B F
A C E G
Stack:
walk(D) [D]
walk(D.left -> B) [D, B]
walk(B.left -> A) [D, B, A]
print(A) [D, B, A]
end of walk A [D, B]
print(B) [D, B]
walk(B.right -> C) [D, B, C]
print(C) [D, B, C]
end of walk C [D, B]
end of B [D]
print(D) [D]
walk(D.right -> F) [D, F]
... ...
Now we unwrap it from recursion:
- Start by walking down into lowest node, adding every node on the way to stack
stack = []
next = root.next
while next:
stack.push(next)
next = next.next
- Pop node from stack, print it. This always prints lowest node and we can assume if there was any lower nodes they had already been processed.
while len(stack) > 0:
node = stack.pop()
print(node.name)
- Every time we print a node, we check if node has "right" - if it does, we repeat step 1 by walking into smallest node and adding it on queue
while len(stack) > 0:
node = stack.pop()
print(node.name)
next = node.right
while(next):
stack.push(next)
next = next.left
Stack size will never exceed the tree height thus it can be allocated prior to iterating.
One good reason why we might want to use recursion unrwapping is so that we could wrap this algorithm with iterator pattern:
class TreeIterator:
__init__(self, root):
self.stack = []
next = root
while(next):
self.stack.push(next)
next = root.next
def next(self):
if(len(self.stack) == 0)
return null
current = self.stack.pop()
next = current.right
while(next):
self.stack.push(next)
next = next.left
return current.key
def main():
tree = {
key: 'D',
left: {key: 'B', left: {key: 'A', right: 'C'}},
right: {key: 'F', left: {key: 'E', right: 'G'}}
}
i = TreeIterator(tree)
while(next = i.next()):
print(next)