Tree Traversals

Tree Traversals

• Similar to iterating over a list
• Often want to visit/process every element in the tree
• But... what makes sense for a tree?
• Trees are unidirectional (no links from child to parent)
• Usually use recursion (run-time stack / backtracking)

Depth-First Traversals

pre-order

• root
• left sub-tree
• right sub-tree

def preOrderTraversal(node):
  if node is null:
    return
  process(node)
  preOrderTraversal(node.left)
  preOrderTraversal(node.right)

     5
    / \
   2   8
  / \   \
 1   3   15
        /  \
       13  22
      /
     12    

Pre-order: 5, 2, 1, 3, 8, 15, 13, 12, 22

in-order

• left sub-tree
• root
• right sub-tree

def inOrderTraversal(node):
  if node is null:
    return

  inOrderTraversal(node.left)
  process(node)
  inOrderTraversal(node.right)

What's so special about running an in-order traversal on a BST?

     5
    / \
   2   8
  / \   \
 1   3   15
        /  \
       13  22
      /
     12  

In-order: 1, 2, 3, 5, 8, 12, 13, 15, 22

post-order

• left sub-tree
• right sub-tree
• root

def postOrderTraversal(node):
  if node is null:
    return

  postOrderTraversal(node.left)
  postOrderTraversal(node.right)
  process(node)

     5
    / \
   2   8
  / \   \
 1   3   15
        /  \
       13  22
      /
     12    

Post-order: 1, 3, 2, 12, 13, 22, 15, 8, 5

Tree Traversal Applet

• http://nova.umuc.edu/~jarc/idsv/lesson1.html

Expression Trees