General Trees

Stacks, queues, arrays, lists, and sequences are all linear structures.
Trees are our first non-linear structure. They are two dimensional, and one of the most important data structures.  Trees will allow us to break through the O(n²) barrier in many problems.

Real Life Examples

• Files and directories

• Company hierarchy

• Decision Trees

• Expression Trees

Terminology

• nodes

• edges

• root node - only one

• parent

• children

• degree of node

• sibling

• external nodes, or leaves – could have empty externals

• internal nodes

• The depth (or level) (root node is at level 0)

• height of tree

Property

m is number of edges and n is the number of nodes then

m = n - 1

Interface

/**
 * An interface for a tree where nodes can have an arbitrary number of children.
 */
public interface Tree {
  /** Returns the number of nodes in the tree. */
  public int size();
  /** Returns whether the tree is empty. */
  public boolean isEmpty();
  /** Return an iterator of the elements stored in the tree. */
  public Iterator elements();
  /** Returns an iterator of the nodes stored in the tree. */
  public Iterator positions();
  /** Replaces the element stored at a given node. */
  public Object replace(Position v, Object e)
    throws InvalidPositionException;
  /** Returns the root of the tree. */
  public Position root() throws EmptyTreeException;
  /** Returns the parent of a given node. */
  public Position parent(Position v)
    throws InvalidPositionException, BoundaryViolationException;
  /** Returns an iterator of the children of a given node. */
  public Iterator children(Position v) 
    throws InvalidPositionException;
  /** Returns whether a given node is internal. */
  public boolean isInternal(Position v) 
    throws InvalidPositionException;
  /** Returns whether a given node is external. */
  public boolean isExternal(Position v) 
    throws InvalidPositionException;
  /** Returns whether a given node is the root of the tree. */
  public boolean isRoot(Position v)
    throws InvalidPositionException;
}

Implementation: Height and depth

Remember: Trees have height and nodes have depth.

Depth

Think recursively.  What is a structure of a recursive algorithm?

Desired_answer recursive(position in the recursion)
    If base case then return base value
    Else return Desired_answer from adjustments to recursive(next position in the recursion)

So recursively call until you get the root and then add one on the way back.

  public static int depth (Tree T, Position v) {
    if (T.isRoot(v))
      return 0;
    else
      return 1 + depth(T, T.parent(v));
  }

Cost is the depth of the node worst case for n for a straggly tree.

Height

Iterative

   public static int height1 (Tree T) {
     int h = 0;
     Iterator positer = T.positions();
     while (positer.hasNext()) {
       Position v = (Position) positer.next();
       if (T.isExternal(v))
         h = Math.max(h, depth(T, v));
     }
     return h;
   }

Worst case cost is O(n²)

Recursive

  public static int height2 (Tree T, Position v) {
    if (T.isExternal(v))
      return 0;
    else {
      int h = 0;
      Iterator children = T.children(v);
      while (children.hasNext())
        h = Math.max(h, height2(T, (Position) children.next()));
      return 1 + h;
    }
  }

Worst case cost is O(n) because the call is made only once at each node.