Explain each traversal in words. import java.util.Iterator; import java.util.List; // for use as snapshot iterator import java.util.ArrayList; // for use as snapshot iterator import java.util.Queue; import java.util.LinkedList; public abstract class AbstractTree implements Tree { /* implements means you are using the elements of a Java Interface in your class. * extends means that you are creating a subclass of the base class you are extending. * You can only extend one class in your child class, * but you can implement as many interfaces as you would like */ // Returns true if Position p has one or more children @Override public boolean isInternal(Position p) { return numChildren(p) > 0;} // Returns true if Position p does not have any children @Override public boolean isExternal(Position p) { return numChildren(p) == 0; } // Returns true if Position p represents the root of the tree @Override public boolean isRoot(Position p) { return p == root(); } // Returns the number of children of Position p. @Override public int numChildren(Position p) { int count = 0; for (Position child : children(p)) {count++;} return count; } // Returns the number of nodes in the tree @Override public int size() { int count=0; for (Position p : positions()) count++; return count; } // Tests whether the tree is empty @Override public boolean isEmpty() { return size() == 0; } // Returns the number of levels separating Position p from the root. public int depth(Position p) throws IllegalArgumentException { if (isRoot(p)) { return 0; } else { return 1 + depth(parent(p));} } // Returns the height of the tree // Note: This implementation works, but runs in O(n^2) worst-case time private int heightBad() { // works, but quadratic worst-case time int h = 0; for (Position p : positions()) if (isExternal(p)) // only consider leaf positions h = Math.max(h, depth(p)); return h; } // Returns the height of the subtree rooted at Position p public int height(Position p) throws IllegalArgumentException { int h = 0; // base case if p is external for (Position c : children(p)) h = Math.max(h, 1 + height(c)); return h; } //---------------- nested ElementIterator class ---------------- /* This class adapts the iteration produced by positions() to return elements. */ private class ElementIterator implements Iterator { Iterator> posIterator = positions().iterator(); public boolean hasNext() { return posIterator.hasNext(); } public T next() { return posIterator.next().getElement(); } // return element! public void remove() { posIterator.remove(); } } // Returns an iterator of the elements stored in the tree @Override public Iterator iterator() { return new ElementIterator(); } // Returns an iterable collection of the positions of the tree @Override public Iterable> positions() { return preorder(); } // Adds positions of the subtree rooted at Position p to the given // snapshot using a preorder traversal private void preorderSubtree(Position p, List> snapshot) { snapshot.add(p); // for preorder, we add position p before exploring subtrees for (Position c : children(p)){preorderSubtree(c, snapshot);} } // Returns an iterable collection of positions of the tree, reported in preorder public Iterable> preorder() { List> snapshot = new ArrayList(); if (!isEmpty()) preorderSubtree(root(), snapshot); // fill the snapshot recursively return snapshot; } // Adds positions of the subtree rooted at Position p to the given // snapshot using a postorder traversal private void postorderSubtree(Position p, List> snapshot) { for (Position c : children(p)) postorderSubtree(c, snapshot); snapshot.add(p); // for postorder, we add position p after exploring subtrees } // Returns an iterable collection of positions of the tree, reported in postorder public Iterable> postorder() { List> snapshot = new ArrayList(); if (!isEmpty()) postorderSubtree(root(), snapshot); // fill the snapshot recursively return snapshot; } // Returns an iterable collection of positions of the tree in breadth-first order public Iterable> breadthfirst() { List> snapshot = new ArrayList(); if (!isEmpty()) { Queue> fringe = new LinkedList>(); fringe.add(root()); // start with the root while (!fringe.isEmpty()) { Position p = fringe.remove(); // remove from front of the queue snapshot.add(p); // report this position for (Position c : children(p)) fringe.add(c); // add children to back of queue } } return snapshot; } } 

// An interface for a binary tree, in which each node has at most two children. public interface BinaryTree extends Tree { // Returns the Position of p's left child (or null if no child exists) Position left(Position p) throws IllegalArgumentException; // Returns the Position of p's right child (or null if no child exists) Position right(Position p) throws IllegalArgumentException; // Returns the Position of p's sibling (or null if no sibling exists) Position sibling(Position p) throws IllegalArgumentException; } 

Analyze the time/space complexity of each tree traversal algorithm: preorder, postorder, inorder, and breath-first. You must explain why you get the results. (on pages 30 to 42 of the 1