Improving BinaryTree The following methods should be implemented for BinaryTree.
ID: 3843964 • Letter: I
Question
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<String> 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 tree’s 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 <T>
*/
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<T> deleteNode() {
if (left == null)
return right;
if (right == null)
return left;
Node<T> 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<T> 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<T> 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<T> 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.
}
}
Explanation / Answer
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 <T>
*/
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<T> deleteNode() {
if (left == null)
return right;
if (right == null)
return left;
Node<T> 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<T> 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<T> 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<T> 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);
}
public Node reachesBothUtil(Node root, T a, T b) {
if (root == null) return null;
if (root.data.equals(a) || root.data.equals(b))
return root;
Node left = reachesBothUtil(root.left, a, b);
Node right = reachesBothUtil(root.right, a, b);
if (left !=null && right!=null)
return root;
return (left != null)? left: right;
}
/**
* 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.
Node result = reachesBothUtil(root, a, b);
if(result!=null)
return (T) result.data;
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.
}
========================
I have implemented the function, have a look
Thanks