Improving BinaryTree

The following methods should be implemented for BinaryTree. Begin with the version of BinaryTreeavailable on Canvas. You will probably have to implement corresponding methods for Node!

1. Implement public T reachesBoth(T a, T b) You should return the data value of the node that can reach both a and b in the least number of steps (anode can reach itself in 0 steps). If a or b is not in the tree, return null. Consider theBinaryTree tree on the left with outputs on the right:

2. Implement public T findRightmostLowest() In the above tree, there are two lowest nodes: B and F. Both of them are distance 3 from the root; allother nodes are less than distance 3. F is to the right of B so tree.findRightmostLowest() should return "F".

3. Implement public T findKthLargest(int k) Consider the sorted order of all the elements in the tree. The index of the smallest element is 0. Theindex of the largest element is tree.size() 1. In the above tree, tree.findKthLargest(1) wouldreturn "D" and tree.findKthLargest(4) would return "H". Return null if k is out of range.

4. EXTRA CREDIT 10 POINTS: Implement public void balance() Use a findKthLargest-based approach to rebalance the tree using a pivot-style approach. The newroot should be the trees median (KthLargest index of size() / 2). Recursively, the root of each branchshould be the median of each branch (index within that subtree of its size / 2). This method should not need to call new and should execute in O(n log n) time to receive full credit.

//Here is BinaryTree.java code so far

import java.util.Arrays;

/** * A binary search tree for Comparable objects such as Strings, Integers, etc. * For each node n, all nodes to the left have data which is less than n.data * and all nodes to the right have data which is greater than n.data. * * @param */ public class BinaryTree> { private static class Node> { public T data; public Node left, right;

public void add(T d) { int comp = d.compareTo(data); if (comp == 0) return; // Already in tree if (comp (); left.data = d; } else { left.add(d); } } else { // Greater than if (right == null) { right = new Node(); right.data = d; } else { right.add(d); } } }

public boolean contains(T d) { int comp = d.compareTo(data); if (comp == 0) return true; // Already in tree if (comp

}

public void print(int indent) { if (right != null) right.print(indent + 1); char[] spaces = new char[indent * 2]; Arrays.fill(spaces, ' '); System.out.println(new String(spaces) + data); if (left != null) left.print(indent + 1); }

/** * The number of nodes of this subtree. * @return Number of nodes */ public int size() { // We know there is a node here int total = 1; // This node may have left children if (left != null) total = total + left.size(); // This node may have right children if (right != null) total = total + right.size(); // The total size of the tree from this point... return total; }

/** * Delete this node. * * @return The new root of this subtree (null if this node had no * children, also known as a leaf) */ public Node deleteNode() { if (left == null) return right; if (right == null) return left; Node successor = right; if (successor.left == null) { // Case 1: no left child of immediate successor right = right.right; } else { // Case 2: loop until we find leftmost child Node successorParent = null; while (successor.left != null) { successorParent = successor; successor = successor.left; } successorParent.left = successor.right; } // Replace this data with successor data data = successor.data; return this; }

/** * Deletes the node containing d if it exists. * * @param d * @return A valid BinaryTree that doesn't have d in it but does have * everything else. */ public Node delete(T d) { int comp = d.compareTo(data); if (comp == 0) return deleteNode(); if (comp

private Node root;

public BinaryTree() { root = null; }

/** * Adds data to the tree if it didn't already contain it. * * @param data */ public void add(T data) { if (root == null) { root = new Node(); root.data = data; } else { root.add(data); } }

/** * Returns true if the tree contains data, false otherwise * * @param data * Does the tree contain this? * @return true if it does */ public boolean contains(T data) { if (root == null) return false; return root.contains(data); }

/** * Prints out a representation of the tree (rotate your head 90 degrees * left) */ public void print() { if (root != null) root.print(0); }

/** * Gets the number of nodes of the tree in O(n) time. * * @return number of nodes */ public int size() { if (root == null) return 0; return root.size(); }

/** * Delete the node containing data from the tree, if it exists. * * @param data */ public void delete(T data) { root = root.delete(data); }

/** * Returns the data value of the node that can reach both a and b in the * least number of steps. If the tree doesn't contain both a and b, return * null. * * @param a * @param b * @return data value */ public T reachesBoth(T a, T b) { // TODO: Implement. return null; }

/** * Among all the nodes which are farthest from the root, find the one which * is farthest to the right. * * @return data value of said node */ public T findRightmostLowest() { // TODO: Implement. return null; }

/** * Return the kth largest element according to the Comparable sorted order * of the tree. The leftmost node has index 0 and the rightmost node has * index size() - 1. * * @param k * index * @return element, or null if k is out of range. */ public T findKthLargest(int k) { // TODO: Implement. return null; }

/** * EXTRA CREDIT: Balance the tree. The new root should be the * findKthLargest(size()/2) node. Recursively, the root of each subtree * should also be the size/2-largest node (indexed from 0) of that subtree. * This method should not call new and should execute in O(n log n) time for * full credit. */ public void balance() { // TODO: Implement for extra credit. } }

tree. reaches Both ("B", "H") would return "G tree reaches Both ("F", "N" would return "M" tree reaches Both ("B", "D") would return "D tree reaches Both ("X", "M") would return null