PreOrder Traversal

Visit the parent node, traverse the left subtree first and then the right subtree. For example,

336px-Sorted_binary_tree_preorder.svg

 

PreOrder: F, B, A, D, C, E, G, I, H

Recursive algorithm

preorder(node)
  visit(node)
  if node.left  ≠ null then preorder(node.left)
  if node.right ≠ null then preorder(node.right)

Iterative algorithm

Preorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null) 
      visit(node)
      if (node.right ≠ null) parentStack.push(node.right) 
      node = node.left   
    else     
      node = parentStack.pop()