Please complete the TreeTraversal?.java file based on the given two java files below:

BinarySearchTree?.java file:

/** * A binary search tree class. * *

* A binary search tree is a binary tree where values are stored in the tree * according to three rules: * *

*
1. values in the left subtree are less than values in the root node *
2. values in the right subtree are greater than or equal to values in the * root node *
3. rules 1 and 2 apply recursively to every subtree *

* * * @param the type of elements in this tree */ public class BinarySearchTree> {

/** * A class that represents nodes in the binary search tree. Each node is an * aggregation of a data element, and has a left and right child node. This * class is a top-level public class for testing purposes only; normally, Node * would be a private inner class. * * @param the type of the data element stored in the node */ public static class Node { private E data; private Node left; private Node right;

/** * Create a node with the given data element. The left and right child nodes * are set to null. * * @param data * the element to store */ public Node(E data) { this.data = data; this.left = null; this.right = null; }

/** * Get the left child node. * * @return the left child node */ public Node left() { return this.left; }

/** * Get the right child node. * * @return the right child node */ public Node right() { return this.right; }

/** * Get the data stored in the node. * * @return the data stored in the node */ public E data() { return this.data; }

/** * Set the left child of this node to the specified node. * * @param left * the left child of this node */ public void setLeft(Node left) { this.left = left; }

/** * Set the right child of this node to the specified node. * * @param right * the right child of this node */ public void setRight(Node right) { this.right = right; }

/** * Set the data of this node to the specified element. * * @param element * the data for this node */ public void setData(E element) { this.data = element; } } private Node root;

/** * Create an empty binary search tree. */ public BinarySearchTree() { this.root = null; }

/** * Add an element to the tree. The element is inserted into the tree in a * position that preserves the definition of a binary search tree. * * @param element * the element to add to the tree */ public void add(E element) { if (this.root == null) { this.root = new Node(element); } else { BinarySearchTree.add(element, this.root); } }

/** * Add an element to the subtree rooted at root. The * element is inserted into the tree in a position that preserves the * definition of a binary search tree. * * @param element * the element to add to the subtree * @param root * the root of the subtree */ private static > void add(E element, Node root) { if (element.compareTo(root.data()) < 0) { if (root.left() == null) { root.setLeft(new Node(element)); } else { BinarySearchTree.add(element, root.left()); } } else { if (root.right() == null) { root.setRight(new Node(element)); } else { BinarySearchTree.add(element, root.right()); } } }

/** * Returns true if the tree contains the given element, * false otherwise. * * @param element * the element to search for * @return true if the tree contains the given element, * false otherwise */ public boolean contains(E element) { return contains(element, this.root); }

/** * Returns true if the subtree rooted at * root contains the given element, false * otherwise. * * @param element * the element to search for * @param root * the root of the subtree * @return true if the subtree rooted at * root contains the given element, * false otherwise */ private static > boolean contains(E element, Node root) { if (root == null) { return false; } if (element.equals(root.data())) { return true; } boolean result; if (element.compareTo(root.data()) < 0) { result = contains(element, root.left()); } else { result = contains(element, root.right()); } return result; }

/** * Return a string representation of the tree. * *

* The string is made up of the elements stored in the tree separated by * commas; the entire list of elements is enclosed in braces. The elements * are in ascending sorted order. * * @see java.lang.Object#toString() * * @return a string representation of the tree */ @Override public String toString() { return "{" + toString(this.root) + "}"; }

/** * Return a string representation of the subtree rooted at * root. * *

* The string is made up of the elements stored in the tree separated by * commas where the elements are in ascending sorted order. * *

* The string is generated using inorder processing of the subtree: * *

*
1. the string corresponding to root.left() is computed *
2. the string corresponding to root.data() is computed *
3. the string corresponding to root.right() is * computed *

* *

* The returned string is the concatenation of the three strings computed by * the inorder processing of the subtree. * * @param root * the root of the subtree * @return the string representation of the subtree */ private static > String toString(Node root) { if (root == null) { return ""; } String left = toString(root.left()); if (!left.isEmpty()) { left = left + ", "; } String right = toString(root.right()); if (!right.isEmpty()) { right = ", " + right; } return left + root.data() + right; }

/** * Get the root node of the tree. For testing purposes only. * * @return the root node of the tree. */ public INode root() { if (this.root == null) { return null; } return new INode(this.root); }

}

INode?.java file:

/** * A class that presents an immutable view of a node of a * binary search tree. While an INode cannot be * used to change the left or right child of a node, it is * possible to change the state of the element stored in the * node if E is a mutable type. * * @param the type of the data element stored in the node */ public class INode {

private BinarySearchTree.Node node; /** * Initializes this node so that it is an aggregation of * the specified BinarySearchTree.Node. * * @param node a BinarySearchTree.Node */ public INode(BinarySearchTree.Node node) { this.node = node; } /** * Get the left child node. * * @return the left child node */ public INode left() { if (this.node.left() == null) { return null; } return new INode(this.node.left()); }

/** * Get the right child node. * * @return the right child node */ public INode right() { if (this.node.right() == null) { return null; } return new INode(this.node.right()); }

/** * Get the data stored in the node. * * @return the data stored in the node */ public E data() { return this.node.data(); } }

This is a TreeTraversal.java file we need to complete based on the above given files (BinarySearchTree?.java and INode?.java):

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 inorder(BinarySearchTree 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 preorder(BinarySearchTree 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 postorder(BinarySearchTree 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 breadthFirst(BinarySearchTree tree) { List result = new ArrayList<>(); INode 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> q = new LinkedList<>();

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 inorder(INode root) { List result = new ArrayList<>(); 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 preorder(INode root) { List result = new ArrayList<>();

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 postorder(INode root) { List result = new ArrayList<>();

return result; }

}