Lab 7 Feedback

Marking scheme:
--------------------

2 / 2  -passes all unit tests AND
       -none or very minor style errors

--------------------

TA Comments:

--------------------

Style checker output:

No style errors found by checkstyle; TAs, please check for poorly named
variables, unusual programming constructs, and other style errors.
--------------------

Unit tester output:

Passed all unit tests.

--------------------

Your submission:

package eecs2030.lab7;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * A utility class that provides methods for traversing a binary
 * search tree.
 *
 */
public class TreeTraversal {
                
        private TreeTraversal() {
                // empty by design
        }

        /**
         * Returns the list of strings formed by traversing the specified tree using
         * an inorder traversal.
         * 
         * @param tree
         *            a binary search tree
         * @return the list of strings formed by traversing the specified tree using
         *         an inorder traversal
         */
        public static List<String> inorder(BinarySearchTree<String> tree) {
                return TreeTraversal.inorder(tree.root());
                // YOU SHOULD IMPLEMENT inorder(INode) below
        }

        /**
         * Returns the list of strings formed by traversing the specified tree using
         * a preorder traversal.
         * 
         * @param tree
         *            a binary search tree
         * @return the list of strings formed by traversing the specified tree using
         *         a preorder traversal
         */
        public static List<String> preorder(BinarySearchTree<String> tree) {
                return TreeTraversal.preorder(tree.root());
                // YOU SHOULD IMPLEMENT preorder(INode) below
        }

        /**
         * Returns the list of strings formed by traversing the specified tree using
         * a postorder traversal.
         * 
         * @param tree
         *            a binary search tree
         * @return the list of strings formed by traversing the specified tree using
         *         a postorder traversal
         */
        public static List<String> postorder(BinarySearchTree<String> tree) {
                return TreeTraversal.postorder(tree.root());
                // YOU SHOULD IMPLEMENT postorder(INode) below
        }

        /**
         * Returns the list of strings formed by traversing the specified tree using
         * a breadth first traversal. The traversal visits nodes of the tree
         * starting at the root moving left to right for each level of the tree.
         * 
         * @param tree
         *            a binary search tree
         * @return the list of strings formed by traversing the specified tree using
         *         a breadth first traversal
         */
        public static List<String> breadthFirst(BinarySearchTree<String> tree) {
                List<String> result = new ArrayList<>();
                INode<String> root = tree.root();
                if (root == null) {
                        return result;
                }

                // in Java, a LinkedList is a Queue
                // to enqueue a node, use the Queue method add
                // to dequeue a node, use the Queue method remove
                Queue<INode<String>> q = new LinkedList<>();
                
                q.add(root);
                while (!q.isEmpty()) {
                        root = q.remove();
                        result.add(root.data());
                        if (root.left() != null)
                                q.add(root.left());
                        if (root.right() != null)
                                q.add(root.right());
                }

                return result;
        }

        /**
         * Returns the list of strings formed by traversing a tree having the
         * specified root using an inorder traversal.
         * 
         * @param root
         *            the root of the tree
         * @return the list of strings formed by traversing a tree having the
         *         specified root using an inorder traversal
         */
        private static List<String> inorder(INode<String> root) {
                List<String> result = new ArrayList<>();
                
                if (root != null) {
                        List<String> left = new ArrayList<>();
                        if (root.left() != null)
                                left = inorder(root.left());
                        result.addAll(left);
                        result.add(root.data());
                        List<String> right = new ArrayList<>();
                        if (root.right() != null)
                                right = inorder(root.right());
                        result.addAll(right);
                }
                
                return result;
        }

        /**
         * Returns the list of strings formed by traversing a tree having the
         * specified root using a preorder traversal.
         * 
         * @param root
         *            the root of the tree
         * @return the list of strings formed by traversing a tree having the
         *         specified root using a preorder traversal
         */
        private static List<String> preorder(INode<String> root) {
                List<String> result = new ArrayList<>();
                
                if (root != null) {
                        result.add(root.data());
                        List<String> left = new ArrayList<>();
                        if (root.left() != null)
                                left = preorder(root.left());
                        result.addAll(left);
                        List<String> right = new ArrayList<>();
                        if (root.right() != null)
                                right = preorder(root.right());
                        result.addAll(right);
                }
                
                return result;
        }

        /**
         * Returns the list of strings formed by traversing a tree having the
         * specified root using a postorder traversal.
         * 
         * @param root
         *            the root of the tree
         * @return the list of strings formed by traversing a tree having the
         *         specified root using a postorder traversal
         */
        private static List<String> postorder(INode<String> root) {
                List<String> result = new ArrayList<>();
                
                if (root != null) {
                        List<String> left = new ArrayList<>();
                        if (root.left() != null)
                                left = postorder(root.left());
                        result.addAll(left);
                        List<String> right = new ArrayList<>();
                        if (root.right() != null)
                                right = postorder(root.right());
                        result.addAll(right);
                        result.add(root.data());
                }

                return result;
        }
        

}