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

Breadth-First Search - Level-Order

• Instead of working our way down one side of the tree, visit nodes by level
• Visit nodes moving from left-to-right, top-to-bottom
• Can use a queue to determine order

def levelOrder(node):
  queue.offer(node)

  while queue is not empty:
    n = queue.poll()
    offer ns children to queue
    process(n)

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

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

Other Traversals

• Can switch order of visiting left, right first
• Can do BFS by visiting right-to-left, top-to-bottom
• Etc.... pre-order, in-order, post-order are most common

Tree Traversal Applet

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

Try-It Out

• Write out the order in which nodes are visited using pre-order, in-order, post-order, and breadth-first level-order for the following tree

         2  
       /   \  
      7      5
     / \      \
    2   6      9
       / \    /
      5  11  4
  

Expression Trees

• Binary tree
• Interior nodes contain operators
• Leaf nodes contain operands
• Depth-first traversals provide prefix, infix, and postfix expression

Pre-order: / + * + 1 2 3 1 2
In-order: 1 + 2 * 3 + 1 / 2 => ((((1 + 2) * 3) + 1) / 2)
Post-order: 1 2 + 3 * 1 + 2 /