Tree Traversal

• Visit all elements
• Different orderings are possible
  • Inorder traversal
  • preorder
  • post order

Inorder Tree Traversal

• Inorder traversal
  • Visit left subtree
  • Visit root
  • Visit right subtree
• In a Binary Search Tree, this gives the nodes in sorted order

Inorder Traversal Example - print

• Print the left subtree of Juliet (tree whose root is Diana)
• Print the root (Juliet)
• Print the right subtree of Juliet (Tom and all its descendants)

12/4 Class Question 1

What is the inorder traversal of the tree

   F
  / \
 D   R
  \
   E

1. FDER
2. EDFR
3. DEFR
4. Something else

Print in order

• The print method

  public void print()
  {
     print(root);
  }

• Calls a recursive helper method with the root as the parameter

  private static void print(Node parent)
  {
     if (parent == null) { return; }
     print(parent.left);
     System.out.print(parent.data + " ");
     print(parent.right);
  }

Preorder/Postorder

• Preorder
  • Visit root
  • Visit the left child
  • Visit the right child
• Postorder
  • Visit the left child
  • Visit the right child
  • Visit root
• For general tree
  • visit all the child nodes left to right

12/4 Class Question 1

What are preorder and postorder traversals of the tree

   F
  / \
 D   R
  \
   E

1. FEDR, DEFR
2. FDER, EDRF
3. DEFR, ERDF
4. something else

Postorder Traversal of Expression Tree

• Postorder traversals

  3 4 + 5 *
  3 4 5 * +

• Gives Reverse Polish Notation of expression
• Useful for in a stack-based calculator

Directory Operations

• Remove a directory and all its children

  

• Can only remove an empty directory
• Must operate on leaves first
• This is postorder

Directory Operations

• Copy a directory and all its children

  

• Must copy the parent before the children
• Start with the root so there is a place to put the children
• This is preorder

12/4 Class Question 2

Suppose you have two directory trees and you want to find out whether they contain the same subdirectories, each of which contains the same files. Should you traverse using

1. inorder
2. preorder
3. postorder
4. preorder or postorder

Visitor Pattern

• What do you want to do when you visit a node
  • Print it?
  • Delete or copy files?
• Create a generic interface

  public interface Visitor
  {
     void visit(Object data);
  }

• private static void preorder(Node n, Visitor v)
  {
     if (n == null) { return; }
     v.visit(n.data);
     for (Node c : n.children) { preorder(c, v); }
  }
  public void preorder(Visitor v) { preorder(root, v); }

Example: Count Short Names

public static void main(String[] args)
{
   BinarySearchTree bst = . . .;
   class ShortNameCounter implements Visitor
   {
      public int counter = 0;
      public void visit(Object data)
      {
         if (data.toString().length() <= 5) { counter++; }
      }
   }
   ShortNameCounter v = new ShortNameCounter();
   bst.preorder(v);
   System.out.println("Short names: " + v.counter);
}

Iteration

• Visitation applies to the entire tree
• Do a certain operation for all nodes
• Iteration is more tentative
• E.g. Get the first ten nodes to display them
• Keep stack of children that must be visited

  Push the root node on a stack.
  While the stack is not empty
   Pop the stack; let n be the popped node.
   Process n.
   Push the children of n on the stack, starting with the last one.

Depth-First Search

Breadth-First Search

12/4 Class Question 3

Suppose you have a binary tree of height n > 1. Can its depth-first traversal ever be the same as its breadth-first traversal?

1. No, never
2. Yes, if it's not a binary search tree
3. Yes, if it has n elements
4. Yes, if the height is 2

 

Tree Iterators

• TreeSet in the Java API has an iterator (inorder traversal)

  TreeSet<String> t = . . .
  Iterator<String> iter = t.iterator();
  String first = iter.next();
  String second = iter.next();

• Note: Does not have a version that takes a Visitor

Tree Iterators

class BreadthFirstIterator
{
   private Queue<Node> q;
   public BreadthFirstIterator(Node root)
   {
      q = new LinkedList<Node>();
      if (root != null) { q.add(root); }
   }
   public boolean hasNext() { return q.size() > 0; }
   public Object next()
   {
      Node n = q.remove();
      for (Node c : n.children) { q.add(c); }
      return n.data;
   }
}