Answered! M H tree reachesBoth ("B", H") would return "G tree. reach ("F", N") would return "M tree. re D") would return "D tree. reachesBoth("X", "M") would return nu…

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<T extends Comparable<T>> {
private static class Node<T extends Comparable<T>> {
public T data;
public Node<T> left, right;
public void add(T d) {
int comp = d.compareTo(data);
if (comp == 0)
return; // Already in tree
if (comp < 0) {
if (left == null) {
left = new Node<>();
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 < 0) {
if (left == null) {
return false; // Not in the tree
} else {
return left.contains(d);
}
} else {
if (right == null) {
return false; // Not in the tree
} else {
return right.contains(d);
}
}
}
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 = (T)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 < 0) {
// If d exists, it’s to the left
if (left != null)
left = left.delete(d);
return this;
} else {
if (right != null)
right = right.delete(d);
return this;
}
}
}
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);
}

/*
This is a recursive helper function to compute reaches both
*/
private T reachesBothAtNode(T a, T b, Node<T> n) {
if(n==null) {
// reached at the bottom and neither a nor b were seen
return null;
}
if(a.compareTo(n.data) == 0) {
// the current node has value a
// if the node contains b anywhere then this is where it reaches both a and b
return n.contains(b) ? a : null;
}
if(b.compareTo(n.data) == 0) {
// the current node has value b
// if the node contains a anywhere then this is where it reaches both a and b
return n.contains(a) ? b : null;
}
if(a.compareTo(n.data) < 0 && b.compareTo(n.data) < 0) {
// both a and b are less than current node value
// if there’s a node that reaches both, it must be in the left subtree
return reachesBothAtNode(a, b, n.left);
}
if(a.compareTo(n.data) > 0 && b.compareTo(n.data) > 0) {
// both a and b are greater than current node value
// if there’s a node that reaches both, it must be in the right subtree
return reachesBothAtNode(a, b, n.right);
}
if(a.compareTo(n.data) < 0 && b.compareTo(n.data) > 0) {
// a is less and b is greater than current node value
// a ‘could’ be in the left and b in right subtree
// if so then our current node reaches both
return (n.left).contains(a) && (n.right).contains(b) ? n.data : null;
}
if(a.compareTo(n.data) > 0 && b.compareTo(n.data) < 0) {
return (n.left).contains(b) && (n.right).contains(a) ? n.data : null;
}
return null;
}

/**
* 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) {
return reachesBothAtNode(a,b,(Node<T>)root);
}

/*
A class to save right most node with its height
height will be required for comparison
*/
private static class RMLWithHeight<T> {
int height;
T data;
public RMLWithHeight(int h,T d) {
height = h;
data = d;
}
}

// recursive helper method for findRightmostLowest of the tree
private RMLWithHeight<T> findRightmostLowestAtNode(Node<T> n) {
if(n.left==null && n.right==null) {
// leaf node height is 0
return new RMLWithHeight(0,n.data);
}
if(n.left == null) {
// no node on left and hence the lowest will always be on the right
RMLWithHeight<T> rmlAtRight = findRightmostLowestAtNode(n.right);
return new RMLWithHeight(rmlAtRight.height+1,rmlAtRight.data);
}
if(n.right == null) {
// no node on right and hence the lowest will always be on the right
RMLWithHeight<T> rmlAtLeft = findRightmostLowestAtNode(n.left);
return new RMLWithHeight(rmlAtLeft.height+1,rmlAtLeft.data);
}
RMLWithHeight<T> rmlAtLeft = findRightmostLowestAtNode(n.left);
RMLWithHeight<T> rmlAtRight = findRightmostLowestAtNode(n.right);
// compare heights of the trees at left and right
// return right most node at left if has a greater height
// also update the height, its one level higher than n.left
if(rmlAtLeft.height > rmlAtRight.height) {
return new RMLWithHeight(rmlAtLeft.height+1,rmlAtLeft.data);
}
// in case right has less or equivalent height, return right most node at right
// also update the height, its one level higher than n.right
return new RMLWithHeight(rmlAtRight.height+1,rmlAtRight.data);
}

/**
* 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() {
RMLWithHeight<T> rml = findRightmostLowestAtNode((Node<T>)root);
return rml.data;
}

public Node<T> findKthLargestAtNode(int k, Node<T> n) {
if(n==null) {
return null;
}
int i = 0; // number of nodes in left sub-tree
if(n.left != null) {
i = (n.left).size();
}

// i is the number of nodes in the tree smaller that the node n
if(i > k) {
// kth smallest element must be less that the current node and hence in the left subtree
return findKthLargestAtNode(k, n.left);
}
if(i == k) {
// kth smallest element is the current node
// since the number of elements less than the current node is k
return n;
}
if(i < k) {
// kth smallest element must be more that the current node
// and hence in the right subtree

// the index of current node is i
// and everything on right is greater that the current node
return findKthLargestAtNode(k-i-1, n.right);
}
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) {
Node<T> knn = findKthLargestAtNode(k,(Node<T>)root);
if (knn == null) {
return null;
}
return knn.data;
}

public void balanceAtNode(Node<T> n, Node<T> parent, boolean isLeft) {
if(n==null) {
return;
}
int k = n.size()/2;

Node<T> mid = findKthLargestAtNode(k,n);

int i=0;
if(mid.left != null) {
i = (mid.left).size();
}

if (mid == n) {
balanceAtNode(mid.left, mid, true);
balanceAtNode(mid.right, mid, false);
} else {
Node

tmp = n;
Node prev = null;
while(true) {
if(mid.data.compareTo((T)tmp.data)<0) {
prev = tmp;
tmp = prev.left;
} else if (mid.data.compareTo((T)tmp.data)>0) {
prev = tmp;
tmp = prev.right;
} else {
break;
}
}
boolean copy_left = true;
if(i==k) {
copy_left = false;
}
if(prev.right == mid) {
if(copy_left) {
prev.right = mid.left;
mid.left = n;
} else {
prev.right = mid.right;
mid.right = n;
}
} else {
if(copy_left) {
prev.left = mid.left;
mid.left = n;
} else {
prev.left = mid.right;
mid.right = n;
}
}

balanceAtNode(mid.left, mid, true);
balanceAtNode(mid.right, mid, false);
}
if(parent == null) {
root = mid;
} else if(isLeft) {
parent.left = mid;
} else {
parent.right = mid;
}
}
/**
* 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() {
balanceAtNode((Node<T>) root, null, true);
}
}

A sample test program:

Ouput screenshot:

sample test program to test the bonus function:

Output screenshot: