Java-data structures P2 Write a method that checks that the underlying tree is a
ID: 3831880 • Letter: J
Question
Java-data structures
P2
Write a method that checks that the underlying tree is a valid binary search tree. The solution should examine each node in the given binary search tree only once.
The header for the method is as follows:
public boolean isBST()
Add the method to the file BinarySearchTree.java
BINARYSEARCHTREE.JAVA
public class BinarySearchTree < T extends Comparable < ? super T >>
{
private BinaryNode<T> root;
public BinarySearchTree () {
root = null;
}
public BinarySearchTree (T rootData) {
root = new BinaryNode<T>(rootData);
}
public T get(T entry) {
return getEntry (root, entry);
}
private T getEntry (BinaryNode<T> rootNode, T entry) {
T result = null;
if (rootNode != null) {
T rootEntry = rootNode.getData ();
if (entry.compareTo(rootEntry) == 0)
result = rootEntry;
else if (entry.compareTo(rootEntry) < 0)
result = getEntry(rootNode.getLeftChild (), entry);
else
result = getEntry(rootNode.getRightChild (), entry);
}
return result;
}
public boolean contains (T entry) {
return get(entry) != null;
}
// Adds newEntry to the nonempty subtree rooted at rootNode.
private T addEntry (BinaryNode< T > rootNode, T newEntry) {
// assume that rootNode is NOT null
T result = null;
int comparison = newEntry.compareTo (rootNode.getData ());
if (comparison == 0) { // duplicates NOT allowed
result = rootNode.getData ();
rootNode.setData (newEntry);
}
else if (comparison < 0) {
if (rootNode.hasLeftChild ())
result = addEntry (rootNode.getLeftChild (), newEntry);
else
rootNode.setLeftChild (new BinaryNode < T > (newEntry));
}
else {
if (rootNode.hasRightChild ())
result = addEntry (rootNode.getRightChild (), newEntry);
else
rootNode.setRightChild (new BinaryNode < T > (newEntry));
} // end if
return result;
} // end addEntry
public T add (T newEntry) {
T result = null;
if (root == null)
root = new BinaryNode<T>(newEntry);
else
result = addEntry (root, newEntry);
return result;
} // end add
class ReturnObject {
T data;
public void set(T newData) { data = newData; }
public T get() { return data; }
}
public T remove (T entry) {
ReturnObject oldEntry = new ReturnObject();
BinaryNode<T> newRoot = removeEntry (root, entry, oldEntry);
root = newRoot;
return oldEntry.get ();
} // end remove
// Removes an entry from the tree rooted at a given node.
// rootNode is a reference to the root of a tree.
// entry is the object to be removed.
// oldEntry is an object whose data field is null.
// Returns the root node of the resulting tree; if entry matches
// an entry in the tree, oldEntry's data field is the entry
// that was removed from the tree; otherwise it is null.
//
// Why removeEntry returns BinaryNode<T>
// Answer: To return a new modified tree: example root node removed so root of tree will change
private BinaryNode<T> removeEntry (BinaryNode<T> rootNode, T entry, ReturnObject oldEntry) {
if (rootNode != null) {
T rootData = rootNode.getData ();
int comparison = entry.compareTo (rootData);
if (comparison == 0) { // entry == root entry
oldEntry.set (rootData);
rootNode = removeFromRoot (rootNode);
}
else if (comparison < 0) { // entry < root entry
BinaryNode<T> leftChild = rootNode.getLeftChild ();
BinaryNode<T> newLeftChild = removeEntry(leftChild, entry, oldEntry);
rootNode.setLeftChild (newLeftChild);
}
else { // entry > root entry
BinaryNode< T > rightChild = rootNode.getRightChild ();
BinaryNode<T> newRightChild = removeEntry (rightChild, entry, oldEntry);
rootNode.setRightChild (newRightChild);
}
}
return rootNode;
}
// Removes the entry in a given root node of a subtree.
// rootNode is the root node of the subtree.
// Returns the root node of the revised subtree.
private BinaryNode<T> removeFromRoot(BinaryNode<T> rootNode)
{
// Case 1: rootNode has two children
if (rootNode.hasLeftChild () && rootNode.hasRightChild ())
{
// find node with largest entry in left subtree
BinaryNode<T> leftSubtreeRoot = rootNode.getLeftChild ();
BinaryNode<T> largestNode = findLargest(leftSubtreeRoot);
// replace entry in root
rootNode.setData (largestNode.getData ());
// remove node with largest entry in left subtree
rootNode.setLeftChild (removeLargest(leftSubtreeRoot));
} // end if
// Case 2: rootNode has at most one child
else if (rootNode.hasRightChild ())
rootNode = rootNode.getRightChild ();
else
rootNode = rootNode.getLeftChild ();
return rootNode;
}
// Finds the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the node containing the largest entry in the tree.
private BinaryNode<T> findLargest (BinaryNode<T> rootNode)
{
if (rootNode.hasRightChild ())
rootNode = findLargest (rootNode.getRightChild ());
return rootNode;
}
// Removes the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the root node of the revised tree.
private BinaryNode<T> removeLargest (BinaryNode<T> rootNode) {
if (rootNode.hasRightChild()) {
BinaryNode<T> rightChild = rootNode.getRightChild ();
BinaryNode<T> root = removeLargest (rightChild);
rootNode.setRightChild (root);
}
else
rootNode = rootNode.getLeftChild ();
return rootNode;
}
}
BINARY NODE.JAVA
//package TreePackage;
class BinaryNode<T> {
private T data;
private BinaryNode<T> left;
private BinaryNode<T> right;
public BinaryNode() {
this(null); // call next constructor
} // end default constructor
public BinaryNode(T dataPortion) {
this(dataPortion, null, null); // call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode<T> leftChild,
BinaryNode<T> rightChild) {
data = dataPortion;
left = leftChild;
right = rightChild;
} // end constructor
public T getData() {
return data;
} // end getData
public void setData(T newData) {
data = newData;
} // end setData
public BinaryNode<T> getLeftChild() {
return left;
} // end getLeftChild
public void setLeftChild(BinaryNode<T> leftChild) {
left = leftChild;
} // end setLeftChild
public boolean hasLeftChild() {
return left != null;
} // end hasLeftChild
public boolean isLeaf() {
return (left == null) && (right == null);
} // end isLeaf
public BinaryNode<T> getRightChild() {
return right;
} // end getLeftChild
public void setRightChild(BinaryNode<T> rightChild) {
right = rightChild;
} // end setLeftChild
public boolean hasRightChild()
{
return right != null;
} // end
public int getHeight()
{
return getHeight(this); // call private getHeight
} // end getHeight
private int getHeight(BinaryNode<T> node)
{
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.left),
getHeight(node.right));
return height;
} // end getHeight
public int getNumberOfNodes()
{
int leftNumber = 0;
int rightNumber = 0;
if (left != null)
leftNumber = left.getNumberOfNodes();
if (right != null)
rightNumber = right.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
} // end BinaryNode
Explanation / Answer
BinarySearchTree.java
package essaydemo;
public class BinarySearchTree < T extends Comparable < ? super T >>
{
private BinaryNode<T> root;
public BinarySearchTree () {
root = null;
}
public BinarySearchTree (T rootData) {
root = new BinaryNode<T>(rootData);
}
public boolean isBST() {
return isBSTUtil(root, getMin(),
getMax());
}
private T getMax()
{
BinaryNode<T> current = root;
/* loop down to find the leftmost leaf */
while (current.getLeftChild() != null) {
current = current.getRightChild();
}
return (current.getData());
}
private T getMin()
{
BinaryNode<T> current = root;
/* loop down to find the leftmost leaf */
while (current.getLeftChild() != null) {
current = current.getLeftChild();
}
return (current.getData());
}
boolean isBSTUtil(BinaryNode<T> node, T min, T max)
{
if (node == null)
return true;
if (node.getData().compareTo(min) < 0 || node.getData().compareTo(max) > 0)
return false;
return (isBSTUtil(node.getLeftChild(), min, node.getData()) &&
isBSTUtil(node.getRightChild(), node.getData(), max));
}
public T get(T entry) {
return getEntry (root, entry);
}
private T getEntry (BinaryNode<T> rootNode, T entry) {
T result = null;
if (rootNode != null) {
T rootEntry = rootNode.getData ();
if (entry.compareTo(rootEntry) == 0)
result = rootEntry;
else if (entry.compareTo(rootEntry) < 0)
result = getEntry(rootNode.getLeftChild (), entry);
else
result = getEntry(rootNode.getRightChild (), entry);
}
return result;
}
public boolean contains (T entry) {
return get(entry) != null;
}
// Adds newEntry to the nonempty subtree rooted at rootNode.
private T addEntry (BinaryNode< T > rootNode, T newEntry) {
// assume that rootNode is NOT null
T result = null;
int comparison = newEntry.compareTo (rootNode.getData ());
if (comparison == 0) { // duplicates NOT allowed
result = rootNode.getData ();
rootNode.setData (newEntry);
}
else if (comparison < 0) {
if (rootNode.hasLeftChild ())
result = addEntry (rootNode.getLeftChild (), newEntry);
else
rootNode.setLeftChild (new BinaryNode < T > (newEntry));
}
else {
if (rootNode.hasRightChild ())
result = addEntry (rootNode.getRightChild (), newEntry);
else
rootNode.setRightChild (new BinaryNode < T > (newEntry));
} // end if
return result;
} // end addEntry
public T add (T newEntry) {
T result = null;
if (root == null)
root = new BinaryNode<T>(newEntry);
else
result = addEntry (root, newEntry);
return result;
} // end add
class ReturnObject {
T data;
public void set(T newData) { data = newData; }
public T get() { return data; }
}
public T remove (T entry) {
ReturnObject oldEntry = new ReturnObject();
BinaryNode<T> newRoot = removeEntry (root, entry, oldEntry);
root = newRoot;
return oldEntry.get ();
} // end remove
// Removes an entry from the tree rooted at a given node.
// rootNode is a reference to the root of a tree.
// entry is the object to be removed.
// oldEntry is an object whose data field is null.
// Returns the root node of the resulting tree; if entry matches
// an entry in the tree, oldEntry's data field is the entry
// that was removed from the tree; otherwise it is null.
//
// Why removeEntry returns BinaryNode<T>
// Answer: To return a new modified tree: example root node removed so root of tree will change
private BinaryNode<T> removeEntry (BinaryNode<T> rootNode, T entry, ReturnObject oldEntry) {
if (rootNode != null) {
T rootData = rootNode.getData ();
int comparison = entry.compareTo (rootData);
if (comparison == 0) { // entry == root entry
oldEntry.set (rootData);
rootNode = removeFromRoot (rootNode);
}
else if (comparison < 0) { // entry < root entry
BinaryNode<T> leftChild = rootNode.getLeftChild ();
BinaryNode<T> newLeftChild = removeEntry(leftChild, entry, oldEntry);
rootNode.setLeftChild (newLeftChild);
}
else { // entry > root entry
BinaryNode< T > rightChild = rootNode.getRightChild ();
BinaryNode<T> newRightChild = removeEntry (rightChild, entry, oldEntry);
rootNode.setRightChild (newRightChild);
}
}
return rootNode;
}
// Removes the entry in a given root node of a subtree.
// rootNode is the root node of the subtree.
// Returns the root node of the revised subtree.
private BinaryNode<T> removeFromRoot(BinaryNode<T> rootNode)
{
// Case 1: rootNode has two children
if (rootNode.hasLeftChild () && rootNode.hasRightChild ())
{
// find node with largest entry in left subtree
BinaryNode<T> leftSubtreeRoot = rootNode.getLeftChild ();
BinaryNode<T> largestNode = findLargest(leftSubtreeRoot);
// replace entry in root
rootNode.setData (largestNode.getData ());
// remove node with largest entry in left subtree
rootNode.setLeftChild (removeLargest(leftSubtreeRoot));
} // end if
// Case 2: rootNode has at most one child
else if (rootNode.hasRightChild ())
rootNode = rootNode.getRightChild ();
else
rootNode = rootNode.getLeftChild ();
return rootNode;
}
// Finds the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the node containing the largest entry in the tree.
private BinaryNode<T> findLargest (BinaryNode<T> rootNode)
{
if (rootNode.hasRightChild ())
rootNode = findLargest (rootNode.getRightChild ());
return rootNode;
}
// Removes the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the root node of the revised tree.
private BinaryNode<T> removeLargest (BinaryNode<T> rootNode) {
if (rootNode.hasRightChild()) {
BinaryNode<T> rightChild = rootNode.getRightChild ();
BinaryNode<T> root = removeLargest (rightChild);
rootNode.setRightChild (root);
}
else
rootNode = rootNode.getLeftChild ();
return rootNode;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.