5.13 Binary Search Tree Implement a BinarySearchTree<E> class which implements t

Question

5.13 Binary Search Tree

Implement a BinarySearchTree<E> class which implements the BinarySearchTreeInterface<E> interface and a BinarySearchTreeNode<E> class which implements BinarySearchTreeNodeInterface<E>. You should not modify the interfaces themselves.

All of the requirements/documentation are included in the comments in the interface classes. Note that in this implementation, the binary search tree node and the binary search tree will be implemented in separate java files (which is different from how we implemented them in class).

Extra credit

You have a huge opportunity to get some extra credit on this assignment. The remove method is extra credit. There are 4 tests for the remove method and 10 tests for all of the other methods. All of the tests will be weighted equally which means that if you passed all of the tests, you would get 140% on this assignment. Some of the remove tests are actually pretty easy so even if you feel like you can't implement remove perfectly, implement some basic cases like removing a leaf node. I recommend you save removing the root node for last because it is the most difficult test to pass.

Interfaces

The interfaces you must implement (and submit because apparently zybooks won't let me just automatically include them) are include below. I'll also post them on canvas.

BinarySearchTreeInterface.java

BinarySearchTreeNodeInterface.java

5.13.1: Binary Search Tree

Submission Instructions

Deliverables

BinarySearchTreeNode.java

BinarySearchTreeInterface.java

BinarySearchTree.java

and

BinarySearchTreeNodeInterface.java

Explanation / Answer

package org.chegg.meenu;

/**

* BinarySearchTree class in Java

* @author Meena

*

*/

public class BinarySearchTree {

class Node {

int key;

Node left, right;

public Node(int item) {

key = item;

left = right = null;

}

}

Node root;

BinarySearchTree() {

root = null;

}

void insert(int key) {

root = insertRec(root, key);

}

Node insertRec(Node root, int key) {

if (root == null) {

root = new Node(key);

return root;

}

if (key < root.key)

root.left = insertRec(root.left, key);

else if (key > root.key)

root.right = insertRec(root.right, key);

return root;

}

void inorder() {

inorderRec(root);

}

void inorderRec(Node root) {

if (root != null) {

inorderRec(root.left);

System.out.println(root.key);

inorderRec(root.right);

}

}

public static void main(String[] args) {

BinarySearchTree tree = new BinarySearchTree();

tree.insert(50);

tree.insert(30);

tree.insert(20);

tree.insert(40);

tree.insert(70);

tree.insert(60);

tree.insert(80);

tree.inorder();

}

}

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.