inorder(root):
walk(node):
if node:
walk(left)
visit node
walk(right)
walk(root)
inorder(root):
# return left, root, right
stack = []
while stack or root:
if root:
add root to stack
go left
else:
get node from stack
visit node
go right
preorder(root):
# return root, left, right
stack = []
while stack or root:
if root:
add root to stack
visit node
go left
else:
get node from stack
go right
postorder(root):
# return left, right, root
# visit in reverse
stack = []
while stack or root:
if root:
add root to stack
visit node
go right
else:
get node from stack
go left
return reverse visited