Here is a summary of a few common implementations of tree traversals.
In order traversal
# recursive
def dfs(root):
if not root:
return
dfs(root.left)
visit(root)
dfs(root.right)
return
# iterative
def inorder(root):
stack = []
node = root
while node or stack:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
visit(node)
node = node.right
pre order
# recursive
def dfs(root):
if not root:
return
visit(root)
dfs(root.left)
dfs(root.right)
# iterative 1
def preorder(root):
stack = [root]
while stack:
node = stack.pop()
visit(node)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# iterative 2
def preorder(root):
stack = []
node = root
while node or stack:
if node:
stack.append(node)
visit(node)
node = node.left
else:
node = stack.pop()
node = node.right
post order
# recursive
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
visit(root)
return
# iterative only visit a node when we know its right child (if exist) has been visited before.
def postorder(root):
last = None
stack = []
node = root
while node or stack:
if node:
stack.append(node)
node = node.left
else:
top = stack[-1]
# its right node has not been visited
if top.right and top.right != last:
node = top.right
stack.append(node)
else:
last = top
visit(top)
# post order = reverse of (pre order (root, right, left))
# code ommitted as an exercise. See discussion 1 for answer.
