Question: Need help with my java project. 2. Implement the add, contains, and remove methods. 3. Complete the block comments for contains and remove methods. 4.

Need help with my java project.

2. Implement the add, contains, and remove methods. 3. Complete the block comments for contains and remove methods. 4. Complete the header comment. 
Recursive definition of Binary Search Tree:

A set of nodes T is a binary search tree if either of the following are true: T is empty If T is not empty, its root node has two subtrees, Tleft and Tright, such that Tleft and Tright are binary search trees and the value in the root node of T is greater than all values in Tleft and is less than all values in Tright. The nodes of the tree are a set (no duplicate values).

Why use a Binary Search Tree?  
The reasoning for storing values in a search tree is to minimize the number of steps required to find the item. In a worst case scenario, we would have to take a number of steps equal to the height of the tree. Ideally the tree is Balanced, meaning both left and right subtrees have about the same height and most of the nodes up until the last level are full. A Complete binary tree is a good example of a Balanced tree. By observing the fact that the number of nodes at each level of the tree double when the tree is Balanced, then the size (n) of the tree is n = 2 ^ height. If we solve for the height of the tree, we get the worst case scenario for searching a balanced tree: O(log n). 
Recursive algorithm for searching a Binary Search Tree:  
1. If the root is null, return false 2. If the target is equal to root.data, return true 3. Else if the target is less than root.data, return the result of searching the left subtree 4. Else return the result of searching the right subtree. 
Keep in mind that the term "root" does not necessarily refer to the root field of the BinarySearchTree.java class. It refers instead to the recursive definition of a binary search tree where every subtree is a binary tree with its own root. 
Example for searching a Binary Search Tree:

lay /\ /\ /\ house rat

/\ /\ /\/\ /\/\

 cow jack milked that 
If we wish to see if the tree contains "jack", first compare "jack" with "lay". Because "jack" is less than "lay", we continue the search with the left subtree and compare "jack" with "house". Because "jack" is greater than "house", we continue with the right subtree and compare "jack" with "jack". Since they are equal, we 
return true. However, if we were searching for "jill", we would have continued down the same path, and seeing that "jill" is greater than "jack", have tried to search the empty subtree on the right and thus concluded "jill" is not in the tree. 
Recursive algorithm for insertion into a Binary Search Tree:  
1. If the root is null, replace empty tree with a new tree with the item at the root and return true 2. Else if the item is equal to the data at the root, then the item is already in the tree; return false 
3. Else if the item is less than root.data, return the result of inserting the item in the left subtree 4. Else return the result of inserting the item in the right subtree

This is a generic algorithm. It does not take into account our particular implementation of the BinarySearchTree class. Implementation options: Option A: Check in advance if the child is null. If it is, assign it a new Node with the given item and return true.

Option B: Do not check in advance if the child is null. Instead, reassign the child to be the result of calling a private add method on the child. Since the public add method returns a boolean, but this strategy returns a Node, you will need to create a global boolean flag which will be used to indicate if the item has been inserted (true) or is a duplicate (false).

For example: private Node add(Node node, E item){ 
 // If node is null, set the flag to true, return a new node with the item // If the item is already in node, set the flag to false, return node // Otherwise, call add(child) on the appropriate subtree of node and then // return the node. i.e. node.left = add(node.left, item); return node;

}

Recursive algorithm for removal from a Binary Search Tree:

1. If the root is null, return false 2. Else if the item is less than the root, return the result of removing from the left subtree 3. Else if the item is greater than the root, return the result of removing from the right subtree 4. Else, the item must equal the root, and the root needs to be removed. 4a. If the root has no children, the root becomes null. 4b. If the root has a single child, the root becomes that child. 4c. If the root has two children, the root becomes the largest value in its left subtree. (Hint: Its called the inorder predecessor and its always located in the same place.) The node containing that value must also be removed. Return true. As with the add method, Options A and B apply here as well.

Tips:

Figure out your base cases (i.e. when you don't recurse). If you have a base case where the given node is null, check that base case first to avoid null pointer exceptions. Use pencil and paper to come up with examples to use for crafting your algorithm. If you hit a bug, use the Debugger to find the problem, then refine your algorithm.

Given code:

import java.util.ArrayList;

/**

* Class for a binary tree that stores type E objects.

*

* @param

* The element type

*/

public class BinaryTree {

static protected class Node {

protected E data;

protected Node left;

protected Node right;

public Node(E data) {

this.data = data;

left = right = null;

}

}

protected Node root;

/**

* Constructs an empty binary tree;

*/

public BinaryTree() {

}

/**

* Constructs a binary tree with the given data at the root.

*

* @param data

* data for the root of the new tree.

*/

public BinaryTree(E data) {

this.root = new Node(data);

}

/**

* Constructs a binary tree with the given data at the root and the two

* given subtrees.

*

* @param data

* data for the root of the new tree.

* @param leftTree

* left binary subtree. Null indicates empty subtree.

* @param rightTree

* right binary subtree Null indicates empty subtree.

*/

public BinaryTree(E data, BinaryTree leftTree, BinaryTree rightTree) {

root = new Node(data);

root.left = leftTree == null ? null : leftTree.root;

root.right = rightTree == null ? null : rightTree.root;

}

/**

* Constructs a binary tree with the given node as the root.

*

* @param root

* root node of the new tree.

*/

protected BinaryTree(Node root) {

this.root = root;

}

/**

* Returns the data held in the root of the tree.

*

* @return data in the root of the tree.

*/

public E getData() {

return root.data;

}

/**

* A tree is a leaf if it has a root and it's left and right subtrees are

* empty (null). An empty tree is not considered to be a leaf.

*

* @return true if tree is a leaf, false otherwise

*/

public boolean isLeaf() {

return isLeaf(root);

}

protected boolean isLeaf(Node root) {

if (root == null) {

return false;

}

return root.left == null && root.right == null;

}

/**

* The height of a tree is the number of nodes in the longest path from the

* root node to a leaf node.

*

* @return the height of the tree

*/

public int getHeight() {

return getHeight(root);

}

protected int getHeight(Node root) {

if (root == null) {

return 0;

}

return 1 + Math.max(getHeight(root.left), getHeight(root.right));

}

public int getSize() {

return getSize(root);

}

protected int getSize(Node root) {

if (root == null) {

return 0;

}

return 1 + getSize(root.left) + getSize(root.right);

}

/**

* Method to return the in-order traversal of the binary tree as a list of

* elements. (Left, Root, Right)

*

* @return A in-order traversal as a string

*/

public ArrayList inOrderTraverse() {

return inOrderTraverse(root);

}

protected ArrayList inOrderTraverse(Node root) {

ArrayList elements = new ArrayList();

if (root == null) {

return elements;

}

elements.addAll(inOrderTraverse(root.left));

elements.add(root.data);

elements.addAll(inOrderTraverse(root.right));

return elements;

}

/**

* Method to return the pre-order traversal of the binary tree as a list of

* elements. (Root, Left, Right)

*

* @return A pre-order traversal as a string

*/

public ArrayList preOrderTraverse() {

return preOrderTraverse(root);

}

protected ArrayList preOrderTraverse(Node root) {

ArrayList elements = new ArrayList();

if (root == null) {

return elements;

}

elements.add(root.data);

elements.addAll(preOrderTraverse(root.left));

elements.addAll(preOrderTraverse(root.right));

return elements;

}

/**

* Method to return the post-order traversal of the binary tree as a list of

* elements. (Left, Right, Root)

*

* @return A post-order traversal as a string

*/

public ArrayList postOrderTraverse() {

return postOrderTraverse(root);

}

protected ArrayList postOrderTraverse(Node root) {

ArrayList elements = new ArrayList();

if (root == null) {

return elements;

}

elements.addAll(postOrderTraverse(root.left));

elements.addAll(postOrderTraverse(root.right));

elements.add(root.data);

return elements;

}

/**

* A binary tree is full if every node has either 0 or 2 children. An empty

* binary tree is not full.

*

* @return true if binary tree is full, false otherwise

*/

public boolean isFull() {

return isFull(root);

}

protected boolean isFull(Node root) {

if (root == null) {

return false;

}

return isLeaf(root) || isFull(root.left) && isFull(root.right);

}

/**

* A complete binary tree is a binary tree whose all levels except the last

* level are completely filled and all the leaves in the last level are all

* to the left side. The empty tree is not a complete tree.

*

* @return true if binary tree is complete, false otherwise

*/

public boolean isComplete() {

int size = getSize();

if (root == null) {

return false;

}

return isComplete(root, 0, size);

}

protected boolean isComplete(Node root, int index, int size) {

if (root == null) {

return true;

}

if (index >= size) {

return false;

}

return isComplete(root.left, 2 * index + 1, size)

&& isComplete(root.right, 2 * index + 2, size);

}

}

Tester code:

import static org.junit.Assert.*;

import org.junit.Test;

import project4.BinaryTree.Node;

public class BinaryTreeTest {

@Test

public void testBinaryTree() {

BinaryTree tree = new BinaryTree();

assertNull(tree.root);

}

@Test

public void testBinaryTreeE() {

BinaryTree tree = new BinaryTree("hi");

assertEquals("hi", tree.root.data);

assertNull(tree.root.right);

assertNull(tree.root.left);

}

@Test

public void testBinaryTreeEBinaryTreeOfEBinaryTreeOfE() {

BinaryTree leftTree = new BinaryTree();

Node leftNode = new Node("left node");

leftTree.root = leftNode;

BinaryTree rightTree = new BinaryTree();

Node rightNode = new Node("right node");

rightTree.root = rightNode;

BinaryTree tree1 = new BinaryTree("tree1", leftTree, rightTree);

assertEquals("tree1", tree1.root.data);

assertEquals(leftTree.root, tree1.root.left);

assertEquals(rightTree.root, tree1.root.right);

BinaryTree tree2 = new BinaryTree("tree2", null, null);

assertNull(tree2.root.right);

assertNull(tree2.root.left);

}

@Test

public void testBinaryTreeNodeOfE() {

Node node = new Node("hi");

BinaryTree tree = new BinaryTree(node);

assertEquals(node, tree.root);

assertEquals("hi", tree.root.data);

}

@Test

public void testGetData() {

Node node = new Node("hi");

BinaryTree tree = new BinaryTree(node);

assertEquals("hi", tree.getData());

}

@Test

public void testIsLeaf() {

BinaryTree tree = new BinaryTree();

/*

* Not Leaf

* empty tree

*/

assertFalse(tree.isLeaf());

/*

* Leaf

* root

*/

Node root = new Node("root");

tree.root = root;

assertTrue(tree.isLeaf());

/*

* Not Leaf

* root

* /

*/

Node child = new Node("child");

tree.root.left = child;

tree.root.right = null;

assertFalse(tree.isLeaf());

/*

* Not Leaf

* root

* \

*/

tree.root.left = null;

tree.root.right = child;

assertFalse(tree.isLeaf());

/*

* Not Leaf

* root

* / \

*/

tree.root.left = child;

tree.root.right = child;

assertFalse(tree.isLeaf());

}

@Test

public void testGetHeight() {

BinaryTree tree = new BinaryTree();

Node root = new Node("node");

Node node2 = new Node("node");

Node node3 = new Node("node");

Node node4 = new Node("node");

Node node5 = new Node("node");

Node node6 = new Node("node");

assertEquals(0, tree.getHeight());

tree.root = root;

assertEquals(1, tree.getHeight());

/*

* 1 root

* 2 /

*/

root.left = node2;

assertEquals(2, tree.getHeight());

/*

* 1 root

* 2 / \

*/

root.right = node3;

assertEquals(2, tree.getHeight());

/*

* 1 root

* 2 / \

* 3 \

*/

node2.right = node4;

assertEquals(3, tree.getHeight());

/*

* 1 root

* 2 / \

* 3 \ /

*/

node3.left = node5;

assertEquals(3, tree.getHeight());

/*

* 1 root

* 2 / \

* 3 \ /

* 4 \

*/

node5.left = node6;

assertEquals(4, tree.getHeight());

}

@Test

public void testGetSize() {

BinaryTree tree = new BinaryTree();

Node root = new Node("node");

Node node2 = new Node("node");

Node node3 = new Node("node");

Node node4 = new Node("node");

Node node5 = new Node("node");

Node node6 = new Node("node");

assertEquals(0, tree.getSize());

tree.root = root;

assertEquals(1, tree.getSize());

/*

* 1 root

* 2 /

*/

root.left = node2;

assertEquals(2, tree.getSize());

/*

* 1 root

* 23 / \

*/

root.right = node3;

assertEquals(3, tree.getSize());

/*

* 1 root

* 23 / \

* 4 \

*/

node2.right = node4;

assertEquals(4, tree.getSize());

/*

* 1 root

* 23 / \

* 45 \ /

*/

node3.left = node5;

assertEquals(5, tree.getSize());

/*

* 1 root

* 23 / \

* 45 \ /

* 6 \

*/

node5.left = node6;

assertEquals(6, tree.getSize());

}

@Test

public void testInOrderTraverse() {

BinaryTree tree = new BinaryTree();

Node node1 = new Node(1);

Node node2 = new Node(2);

Node node3 = new Node(3);

Node node4 = new Node(4);

Node node5 = new Node(5);

tree.root = node1;

node1.left = node2;

node1.right = node3;

node2.left = node4;

node2.right = node5;

Integer[] expecteds = {4, 2, 5, 1, 3};

Integer[] actuals = new Integer[5];

actuals = tree.inOrderTraverse().toArray(actuals);

assertArrayEquals(expecteds, actuals);

}

@Test

public void testPreOrderTraverse() {

BinaryTree tree = new BinaryTree();

Node node1 = new Node(1);

Node node2 = new Node(2);

Node node3 = new Node(3);

Node node4 = new Node(4);

Node node5 = new Node(5);

tree.root = node1;

node1.left = node2;

node1.right = node3;

node2.left = node4;

node2.right = node5;

Integer[] expecteds = {1, 2, 4, 5, 3};

Integer[] actuals = new Integer[5];

actuals = tree.preOrderTraverse().toArray(actuals);

assertArrayEquals(expecteds, actuals);

}

@Test

public void testPostOrderTraverse() {

BinaryTree tree = new BinaryTree();

Node node1 = new Node(1);

Node node2 = new Node(2);

Node node3 = new Node(3);

Node node4 = new Node(4);

Node node5 = new Node(5);

tree.root = node1;

node1.left = node2;

node1.right = node3;

node2.left = node4;

node2.right = node5;

Integer[] expecteds = {4, 5, 2, 3, 1};

Integer[] actuals = new Integer[5];

actuals = tree.postOrderTraverse().toArray(actuals);

assertArrayEquals(expecteds, actuals);

}

@Test

public void testIsFull() {

BinaryTree tree = new BinaryTree();

/*

* Not Full

* empty tree

*/

assertFalse(tree.isFull());

/*

* Full

* root

*/

Node root = new Node("node");

tree.root = root;

assertTrue(tree.isFull());

/*

* Not Full

* root

* /

*/

Node node2 = new Node("node");

root.left = node2;

assertFalse(tree.isFull());

/*

* Full

* root

* / \

*/

Node node3 = new Node("node");

root.right = node3;

assertTrue(tree.isFull());

/*

* Not Full

* root

* / \

* /

*/

Node node4 = new Node("node");

node2.left = node4;

assertFalse(tree.isFull());

/*

* Full

* root

* / \

* /\

*/

Node node5 = new Node("node");

node2.right = node5;

assertTrue(tree.isFull());

/*

* Not Full

* root

* \

* /\

*/

root.left = null;

root.right = node2;

assertFalse(tree.isFull());

/*

* Full

* root

* / \

* /\

*/

root.left = node3;

assertTrue(tree.isFull());

}

@Test

public void testIsComplete() {

BinaryTree tree = new BinaryTree();

/*

* Not Complete

* empty tree

*/

assertFalse(tree.isComplete());

/*

* Complete

* root (0)

*/

Node node0 = new Node("node");

tree.root = node0;

assertTrue(tree.isComplete());

/*

* Complete

* 0

* /

* 1

*/

Node node1 = new Node("node");

node0.left = node1;

assertTrue(tree.isComplete());

/*

* Complete

* 0

* / \

* 1 2

*/

Node node2 = new Node("node");

node0.right = node2;

assertTrue(tree.isComplete());

/*

* Complete

* 0

* / \

* 1 2

* /

* 3

*/

Node node3 = new Node("node");

node1.left = node3;

assertTrue(tree.isComplete());

/*

* Complete

* 0

* / \

* 1 2

* / \

* 3 4

*/

Node node4 = new Node("node");

node1.right = node4;

assertTrue(tree.isComplete());

/*

* Complete

* 0

* / \

* 1 2

* /\ /

* 3 4 5

*/

Node node5 = new Node("node");

node2.left = node5;

assertTrue(tree.isComplete());

/*

* Not Complete

* 0

* / \

* 1 2

* \ /

* 4 5

*/

node1.left = null;

assertFalse(tree.isComplete());

/*

* Not Complete

* 0

* / \

* 1 2

* / \

* 5 6

*/

node1.right = null;

Node node6 = new Node("node");

node2.right = node6;

assertFalse(tree.isComplete());

}

}

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Q:

Help with a java project please: User Request "Create a simple system to read, search, remove, and write restaurant data." Objectives: 1. 2. 3. 4. 5. 10 points 10 points Use standard Java I/O to...

Q:

Hi, I need some help with this java project. Thank you! Here is the prompt; it has three parts: In this assignment, write code to analyze a string character-by-character and return the field values...

Q:

I need help with part F for drawing a UML class diagram for the Student class. I don't know how to create that diagram. Make sure that you list all of the fields and methods in the diagram. Also,...

Q:

need help with this java project This project provides an opportunity to practice object oriented programming. The intent of this project is to create an object model of a bingo game, and implement...

Q:

Given the problem statement below, complete the following A class for CrosswordPuzzle ADT that meets all requirements listed in this description. In order to receive credit, your code MUST (80 pts) o...

Q:

Help with a java project: Must have at least 6 classes. Description For this project, you will put together several techniques and concepts you have learned in CS 210 (or from a similar background)...

Q:

Assignment 2 Information City Coffee House City Coffee House Home Menu Events Event Registration Relax at City Coffee Friendly and eclectic - City Coffee House is the perfect place to take a break,...

Q:

I need help in multiple codes that work together with inheritance... this is a very lengthy question, and for that, I am sorry. I put my java code through a tester program and I am getting errors...

Q:

1. Download the following source files: - Deck.java - DeckInterface.java - Card.java - WarCardGame.java (Note: The only class you need to implement.) 2. In Eclipse, create a new Java project called...

Q:

In this project, you will be practicing the use of Java lists and enum types by im-plementing a command line Blackjack game. Using the classes Card and CardDeck, which will be provided, you will...

Q:

If 12.0 ml. of 8.30104M Ba(CH3CO0), are added to 15.0 mL. of 1.10105 M (NH4)2Co, will solid BaCO3 (Kp 8.1x10) precipitate? If a precipitate will not form, what carbonate ion concentration will cause...

Q:

Given the following data set: 2.3, 1.0, 2.1, 6.5, 2.8, 8.8, 1.7, 2.9, 4.4, 5.1, 2.0 a. Find the positions of the lower and upper quartiles. b. Sort the data from smallest to largest and find the...

Q:

1 6 In 2 0 2 0 , the Form 1 0 4 0 is not appropriate for someone who: Multiple Choice 0 0 : 3 3 : 2 3 is single with no children. makes less than $ 5 0 , 0 0 0 with no interest or dividends. has a...

Q:

Seved Help 14 Wisconsin Snowmobile Corp. is considering a switch to level production Cost efficiencies would occur under level production, and aftertax costs would decline by $31,500, but inventory...

Q:

If the tax rate is 40 percent, compute the beforetax real interest rate and the after-tax real interest rate in each of the following cases. a. The nominal interest rate is 10 percent and the...

Q:

Assume that the reserve requirement is 20%. Also assume that banks do not hold excess reserves and there is no cash held by the public. The Federal Reserve decides that it wants to expand the money...

Q:

It is often suggested that the Federal Reserve try to achieve zero inflation. If we assume that velocity is constant, does this zero-inflation goal require that the rate of money growth equal zero?...