·
Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root,
left, right)
·
In-order traversal sequence: A, B, C, D, E, F, G, H, I (left,
root, right)
·
Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left,
right, root)
Breadth-first
·
Implementations
Depth-first
In-order
inorder(node)
if node == null then return
inorder(node.left)
visit(node)
inorder(node.right)
iterativeInorder(node)
parentStack = empty stack
while not parentStack.isEmpty() or node != null
if node != null then
parentStack.push(node)
node = node.left
else
node = parentStack.pop()
visit(node)
node = node.right
Pre-order
preorder(node)
if node == null then return
visit(node)
preorder(node.left)
preorder(node.right)
iterativePreorder(node)
parentStack = empty stack
while not parentStack.isEmpty() or node != null
if node != null then
visit(node)
parentStack.push(node.right)
node = node.left
else
node = parentStack.pop()
Post-order
postorder(node)
if node == null then return
postorder(node.left)
postorder(node.right)
visit(node)
iterativePostorder(node)
if node == null then return
nodeStack.push(node)
prevNode = null
while not nodeStack.isEmpty()
currNode = nodeStack.peek()
if prevNode == null or prevNode.left == currNode or prevNode.right == currNode
if currNode.left != null
nodeStack.push(currNode.left)
else if currNode.right != null
nodeStack.push(currNode.right)
else if currNode.left == prevNode
if currNode.right != null
nodeStack.push(currNode.right)
else
visit(currNode)
nodeStack.pop()
prevNode = currNode
