I am able to understand preorder traversal without using recursion, but I'm having a hard time with inorder traversal. I just don't seem to get it, perhaps, because I haven't understood the inner working of recursion.
This is what I've tried so far:
def traverseInorder(node):
lifo = Lifo()
lifo.push(node)
while True:
if node is None:
break
if node.left is not None:
lifo.push(node.left)
node = node.left
continue
prev = node
while True:
if node is None:
break
print node.value
prev = node
node = lifo.pop()
node = prev
if node.right is not None:
lifo.push(node.right)
node = node.right
else:
break
The inner while-loop just doesn't feel right. Also, some of the elements are getting printed twice; may be I can solve this by checking if that node has been printed before, but that requires another variable, which, again, doesn't feel right. Where am I going wrong?
I haven't tried postorder traversal, but I guess it's similar and I will face the same conceptual blockage there, too.
Thanks for your time!
P.S.: Definitions of Lifo and Node:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
class Lifo:
def __init__(self):
self.lifo = ()
def push(self, data):
self.lifo = (data, self.lifo)
def pop(self):
if len(self.lifo) == 0:
return None
ret, self.lifo = self.lifo
return ret
Start with the recursive algorithm (pseudocode) :
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
This is a clear case of tail recursion, so you can easily turn it into a while-loop.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
You're left with a recursive call. What the recursive call does is push a new context on the stack, run the code from the beginning, then retrieve the context and keep doing what it was doing. So, you create a stack for storage, and a loop that determines, on every iteration, whether we're in a "first run" situation (non-null node) or a "returning" situation (null node, non-empty stack) and runs the appropriate code:
traverse(node):
stack = []
while !empty(stack) || node != None do:
if node != None do: // this is a normal call, recurse
push(stack,node)
node = node.left
else // we are now returning: pop and print the current node
node = pop(stack)
print node.value
node = node.right
endif
endwhile
The hard thing to grasp is the "return" part: you have to determine, in your loop, whether the code you're running is in the "entering the function" situation or in the "returning from a call" situation, and you will have an if/else chain with as many cases as you have non-terminal recursions in your code.
In this specific situation, we're using the node to keep information about the situation. Another way would be to store that in the stack itself (just like a computer does for recursion). With that technique, the code is less optimal, but easier to follow
traverse(node):
// entry:
if node == NULL do return
traverse(node.left)
// after-left-traversal:
print node.value
traverse(node.right)
traverse(node):
stack = [node,'entry']
while !empty(stack) do:
[node,state] = pop(stack)
switch state:
case 'entry':
if node == None do: break; // return
push(stack,[node,'after-left-traversal']) // store return address
push(stack,[node.left,'entry']) // recursive call
break;
case 'after-left-traversal':
print node.value;
// tail call : no return address
push(stack,[node.right,'entry']) // recursive call
end
endwhile