Submit SearchTree.java (Given) with the following method added:

countSameData(SearchTree other); a public method that counts the number of tree nodes containing the same data, as determined by compareTo()==0. See example below.

Explanation: I accomplished this by building upon many things we've done this quarter, recursion, tree traversals, and even java.util.* (yes import that if needed).

Since this BST requires Comparable, you must rely on .compareTo in case someone wants to use CalendarDate or String data for

Order of data in the tree does not matter, just counting same data nodes, also knowing that trees can be empty, or compared to itself, as example below demonstrates:

SearchTree zero = new SearchTree(); SearchTree one = new SearchTree(); SearchTree two = new SearchTree(); one.add(9); one.add(8); one.add(7); // all left nodes two.add(7); two.add(8); two.add(9); // all right nodes System.out.println(one.equals(two)); // false System.out.println(one.countSameData(two)); // 3 System.out.println(one.countSameData(one)); // 3 System.out.println(zero.countSameData(two)); // 0 two.remove(8); System.out.println(one.countSameData(two)); // 2 

SearchTree.java:

// Class SearchTree stores and prints a binary search tree of // objects of type E. E must implement the Comparable // interface. from Reges and Stepp, BJP 3ed.

public class SearchTree> { private SearchTreeNode overallRoot; // root of overall tree

// post: constructs an empty search tree public SearchTree() { overallRoot = null; } // WRITE ADDITIONAL METHODS HERE:

//END

// post: value added to tree so as to preserve binary search tree public void add(E value) { overallRoot = add(overallRoot, value); }

// post: value added to tree so as to preserve binary search tree private SearchTreeNode add(SearchTreeNode root, E value) { if (root == null) { root = new SearchTreeNode(value); } else if (root.data.compareTo(value) > 0) { root.left = add(root.left, value); } else if (root.data.compareTo(value) < 0) { root.right = add(root.right, value); } return root; }

// post: returns true if tree contains value, returns false otherwise public boolean contains(E value) { return contains(overallRoot, value); }

// post: returns true if given tree contains value, returns false otherwise private boolean contains(SearchTreeNode root, E value) { if (root == null) { return false; } else { int compare = value.compareTo(root.data); if (compare == 0) { return true; } else if (compare < 0) { return contains(root.left, value); } else { // compare > 0 return contains(root.right, value); } } }

// post: prints the data of the tree, one per line public void print() { printInorder(overallRoot); }

// post: prints the data of the tree using an inorder traversal private void printInorder(SearchTreeNode root) { if (root != null) { printInorder(root.left); System.out.println(root.data); printInorder(root.right); } }

private static class SearchTreeNode { public E data; // data stored in this node public SearchTreeNode left; // left subtree public SearchTreeNode right; // right subtree

// post: constructs a leaf node with given data public SearchTreeNode(E data) { this(data, null, null); }

// post: constructs a node with the given data and links public SearchTreeNode(E data, SearchTreeNode left, SearchTreeNode right) { this.data = data; this.left = left; this.right = right; } } }