# BST problem (Online waiting)

hong Li

Greenhorn

Posts: 4

posted 8 years ago

This is my assignemt, I passed all except one, I have been fixing for ages still cant fix, please help. it's due tomorrow

Due Date: Friday May 16th

Submission Instructions: Submit your files via Moodle

What to Submit: MyBST.java file

For this assignment you are required to implement a binary search tree, called

MyBST.java which implements the BST.java interface. Your tree must allow

duplicates to be stored and to this end each node in the tree has a counter that

represents the number of copies of each number (just as in the linked list you

implemented for the last assignment).

Use the BSTNode class to represent the nodes in the tree.

For simplicity, your implementation does not need to support deletion of el-

ements from the tree. The methods you must implement are given in the BST

interface. You must implement a class called MyBST that implements this in-

terface. Make sure your class passes the tests in Test5.

NB: You must implement this class yourself and not use a built in library

or one you�ve found.

The BST.java interface and BSTNode.java classes are provided for you, you

must not change these in any way. The BST interface describes how each of

the functions you are required to implement are supposed to work. A test class

called Test5 is provided which can be used to test your binary search tree works

correctly, if you build your tree correctly when you run Test5 all tests are passed.

To complete this assignment you must:

1. Create a class called MyBST.java which implements the BST interface

2. Write all of the required methods given by the interface

3. Ensure that your list passes all of the tests in Test5

This assignment is worth 10% of your final grade, marks will be allocated as

follows:

� Creating MyBST class with all of the required fields and methods − 1

mark

� Correctly implementing top method − 1 mark

� Correctly implementing insert method − 2 marks

� Correctly implementing output method − 2 marks

� Correctly implementing find method − 2 marks

� Code structure and comments − 2 marks

If you are unclear about any of this information, please ask.

import java.util.ArrayList;

/**

* This is the interface you must implement to complete the assignment.

*

* It is an interface to a binary search tree for storing integers,

* supporting insertion and output. The BST must support insertion

* of duplicate elements (by maintaining a counter at each node).

*

* Obviously, a real implementation would normally also require a method

* for deleting elements from the tree. This is omitted here for

* simplicity.

*

* The last method wouldn't be present in an actual real-world

* implementation, but you must implement it so that we can test

* that your program builds binary search trees with the correct

* structure.

*

* @author Ian McDonald

*/

public interface BST {

/**

* Insert an integer into the BST.

*

* This must create a node if the number doesn't already exist and put

* it in correct place. If it does exist then it must add 1 to the count.

*

* @param n the integer to add

*/

void insert(int n);

/**

* This method must output the content of the BST into an ArrayList. The

* integers must be output in correct order (i.e. do not sort the ArrayList after

* adding the items). If the counter for a number

* in the BST is N, then this number must be output N times.

*

* @return an array list containing the list of integers

*/

ArrayList<Integer> output();

/**

* This method gets the top of the tree.

*

* @returnthe top of the tree or null if empty

*/

BSTNode top();

/**

*

* This recursive method searches the tree for a given value and returns true if the value is

* found and false if it is not found. The method must be defined recursively

* @param an int which isthe value to find

* @param BSTNode the root of the current tree

* @return true or false

*/

boolean find(int n, BSTNode r);

}

/**

* This class contains the basic node structure for the binary search tree.

*/

public class BSTNode {

// Reference to left node

private BSTNode left;

// Reference to right node

private BSTNode right;

// The data stored at the node

private Integer data;

// The number of data items stored at the node

private Integer count;

/**

* The default constructor.

*

* Initializes count to one.

*/

public BSTNode() {

count = 1;

}

/**

* Constructor that takes data.

*

* Initializes count to one.

*

* @param data the data

* @param left a reference to the left node

*/

public BSTNode(Integer data, BSTNode left, BSTNode right) {

this();

this.data = data;

this.left = left;

this.right = right;

}

/**

* @return the count

*/

public Integer getCount() {

return count;

}

/**

* @param count the count to increment

*/

public void increment() {

this.count++;

}

/**

* @return the data

*/

public Integer getData() {

return data;

}

/**

* @param data the data to set

*/

public void setData(Integer data) {

this.data = data;

}

/**

* @return the left node

*/

public BSTNode getLeft() {

return left;

}

/**

* @param left the left node to set

*/

public void setLeft(BSTNode left) {

this.left = left;

}

/**

* @return the right node

*/

public BSTNode getRight() {

return right;

}

/**

* @param right the right node to set

*/

public void setRight(BSTNode right) {

this.right = right;

}

}

import java.util.*;

public class Test5 {

/**

* Checks whether given tree has BST property. Assumes that given

* root is not null.

*

* @param node the root of the subtree to check

* @param minAndMax two-element array that contains minimum and maximum

* value of subtree when method returns

* @return true if the subtree satisfies BST property and false otherwise

*/

public static boolean checkBSTProperty(BSTNode root, int[] minAndMax) {

// Array to hold minimum and maximum from left subtree

int[] minAndMaxLeft = new int[2];

// Checks based on left subtree

if (root.getLeft() != null) {

if (!checkBSTProperty(root.getLeft(), minAndMaxLeft)) {

// Property does not hold for left subtree

return false;

} else if (root.getData() <= minAndMaxLeft[1]) {

// Property does not hold for current node

// because current number is not greater than

// maximum from left subtree

return false;

}

}

// Array to hold minimum and maximum from righ subtree

int[] minAndMaxRight = new int[2];

// Checks based on right subtree

if (root.getRight() != null) {

if (!checkBSTProperty(root.getRight(), minAndMaxRight)) {

// Property does not hold for right subtree

return false;

} else if (root.getData() >= minAndMaxRight[0]) {

// Property does not hold for current node

// because current number is not smaller than

// minimum from right subtree

return false;

}

}

// Compute minimum and maximum for current subtree

// based on the fact that current subtree has BST property

if (root.getRight() != null) {

minAndMax[1] = minAndMaxRight[1];

} else {

minAndMax[1] = root.getData();

}

if (root.getLeft() != null) {

minAndMax[0] = minAndMaxLeft[0];

} else {

minAndMax[0] = root.getData();

}

// This subtree checks out

return true;

}

/**

* The main method with test case.

* @param args

*/

public static void main(String[] args) {

MyBST m = new MyBST();

if (m.top() == null)

System.out.println("PASS top() works on empty tree");

else

System.out.println("FAIL top() fails on empty tree");

m.insert(5);

m.insert(3);

m.insert(7);

m.insert(5);

m.insert(2);

m.insert(9);

m.insert(5);

m.insert(2);

BSTNode top = m.top();

if (top != null) {

System.out.println("PASS root node exists");

} else {

System.out.println("FAIL root node does not exist");

}

if (checkBSTProperty(top, new int[2])) {

System.out.println("PASS tree has BST property");

} else {

System.out.println("FAIL tree does not have BST property");

}

if(m.find(9, top))

System.out.println("PASS found value 9");

else

System.out.println("FAIL did not find value 9");

if(m.find(6, top))

System.out.println("FAIL returned true when searching for 6");

else

System.out.println("PASS did not find value 6");

ArrayList<Integer> il = m.output();

ArrayList<Integer> correctOutput = new ArrayList<Integer>();

Integer[] arr = {2, 2, 3, 5, 5, 5, 7, 9};

correctOutput.addAll(Arrays.asList(arr));

if (il.equals(correctOutput)) {

System.out.println("PASS output is correct");

} else {

System.out.println("FAIL output is not correct");

}

}

}

[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]

Due Date: Friday May 16th

Submission Instructions: Submit your files via Moodle

What to Submit: MyBST.java file

For this assignment you are required to implement a binary search tree, called

MyBST.java which implements the BST.java interface. Your tree must allow

duplicates to be stored and to this end each node in the tree has a counter that

represents the number of copies of each number (just as in the linked list you

implemented for the last assignment).

Use the BSTNode class to represent the nodes in the tree.

For simplicity, your implementation does not need to support deletion of el-

ements from the tree. The methods you must implement are given in the BST

interface. You must implement a class called MyBST that implements this in-

terface. Make sure your class passes the tests in Test5.

NB: You must implement this class yourself and not use a built in library

or one you�ve found.

The BST.java interface and BSTNode.java classes are provided for you, you

must not change these in any way. The BST interface describes how each of

the functions you are required to implement are supposed to work. A test class

called Test5 is provided which can be used to test your binary search tree works

correctly, if you build your tree correctly when you run Test5 all tests are passed.

To complete this assignment you must:

1. Create a class called MyBST.java which implements the BST interface

2. Write all of the required methods given by the interface

3. Ensure that your list passes all of the tests in Test5

This assignment is worth 10% of your final grade, marks will be allocated as

follows:

� Creating MyBST class with all of the required fields and methods − 1

mark

� Correctly implementing top method − 1 mark

� Correctly implementing insert method − 2 marks

� Correctly implementing output method − 2 marks

� Correctly implementing find method − 2 marks

� Code structure and comments − 2 marks

If you are unclear about any of this information, please ask.

**BST**fileimport java.util.ArrayList;

/**

* This is the interface you must implement to complete the assignment.

*

* It is an interface to a binary search tree for storing integers,

* supporting insertion and output. The BST must support insertion

* of duplicate elements (by maintaining a counter at each node).

*

* Obviously, a real implementation would normally also require a method

* for deleting elements from the tree. This is omitted here for

* simplicity.

*

* The last method wouldn't be present in an actual real-world

* implementation, but you must implement it so that we can test

* that your program builds binary search trees with the correct

* structure.

*

* @author Ian McDonald

*/

public interface BST {

/**

* Insert an integer into the BST.

*

* This must create a node if the number doesn't already exist and put

* it in correct place. If it does exist then it must add 1 to the count.

*

* @param n the integer to add

*/

void insert(int n);

/**

* This method must output the content of the BST into an ArrayList. The

* integers must be output in correct order (i.e. do not sort the ArrayList after

* adding the items). If the counter for a number

* in the BST is N, then this number must be output N times.

*

* @return an array list containing the list of integers

*/

ArrayList<Integer> output();

/**

* This method gets the top of the tree.

*

* @returnthe top of the tree or null if empty

*/

BSTNode top();

/**

*

* This recursive method searches the tree for a given value and returns true if the value is

* found and false if it is not found. The method must be defined recursively

* @param an int which isthe value to find

* @param BSTNode the root of the current tree

* @return true or false

*/

boolean find(int n, BSTNode r);

}

**BSTNode**file/**

* This class contains the basic node structure for the binary search tree.

*/

public class BSTNode {

// Reference to left node

private BSTNode left;

// Reference to right node

private BSTNode right;

// The data stored at the node

private Integer data;

// The number of data items stored at the node

private Integer count;

/**

* The default constructor.

*

* Initializes count to one.

*/

public BSTNode() {

count = 1;

}

/**

* Constructor that takes data.

*

* Initializes count to one.

*

* @param data the data

* @param left a reference to the left node

*/

public BSTNode(Integer data, BSTNode left, BSTNode right) {

this();

this.data = data;

this.left = left;

this.right = right;

}

/**

* @return the count

*/

public Integer getCount() {

return count;

}

/**

* @param count the count to increment

*/

public void increment() {

this.count++;

}

/**

* @return the data

*/

public Integer getData() {

return data;

}

/**

* @param data the data to set

*/

public void setData(Integer data) {

this.data = data;

}

/**

* @return the left node

*/

public BSTNode getLeft() {

return left;

}

/**

* @param left the left node to set

*/

public void setLeft(BSTNode left) {

this.left = left;

}

/**

* @return the right node

*/

public BSTNode getRight() {

return right;

}

/**

* @param right the right node to set

*/

public void setRight(BSTNode right) {

this.right = right;

}

}

**Test5**fileimport java.util.*;

public class Test5 {

/**

* Checks whether given tree has BST property. Assumes that given

* root is not null.

*

* @param node the root of the subtree to check

* @param minAndMax two-element array that contains minimum and maximum

* value of subtree when method returns

* @return true if the subtree satisfies BST property and false otherwise

*/

public static boolean checkBSTProperty(BSTNode root, int[] minAndMax) {

// Array to hold minimum and maximum from left subtree

int[] minAndMaxLeft = new int[2];

// Checks based on left subtree

if (root.getLeft() != null) {

if (!checkBSTProperty(root.getLeft(), minAndMaxLeft)) {

// Property does not hold for left subtree

return false;

} else if (root.getData() <= minAndMaxLeft[1]) {

// Property does not hold for current node

// because current number is not greater than

// maximum from left subtree

return false;

}

}

// Array to hold minimum and maximum from righ subtree

int[] minAndMaxRight = new int[2];

// Checks based on right subtree

if (root.getRight() != null) {

if (!checkBSTProperty(root.getRight(), minAndMaxRight)) {

// Property does not hold for right subtree

return false;

} else if (root.getData() >= minAndMaxRight[0]) {

// Property does not hold for current node

// because current number is not smaller than

// minimum from right subtree

return false;

}

}

// Compute minimum and maximum for current subtree

// based on the fact that current subtree has BST property

if (root.getRight() != null) {

minAndMax[1] = minAndMaxRight[1];

} else {

minAndMax[1] = root.getData();

}

if (root.getLeft() != null) {

minAndMax[0] = minAndMaxLeft[0];

} else {

minAndMax[0] = root.getData();

}

// This subtree checks out

return true;

}

/**

* The main method with test case.

* @param args

*/

public static void main(String[] args) {

MyBST m = new MyBST();

if (m.top() == null)

System.out.println("PASS top() works on empty tree");

else

System.out.println("FAIL top() fails on empty tree");

m.insert(5);

m.insert(3);

m.insert(7);

m.insert(5);

m.insert(2);

m.insert(9);

m.insert(5);

m.insert(2);

BSTNode top = m.top();

if (top != null) {

System.out.println("PASS root node exists");

} else {

System.out.println("FAIL root node does not exist");

}

if (checkBSTProperty(top, new int[2])) {

System.out.println("PASS tree has BST property");

} else {

System.out.println("FAIL tree does not have BST property");

}

if(m.find(9, top))

System.out.println("PASS found value 9");

else

System.out.println("FAIL did not find value 9");

if(m.find(6, top))

System.out.println("FAIL returned true when searching for 6");

else

System.out.println("PASS did not find value 6");

ArrayList<Integer> il = m.output();

ArrayList<Integer> correctOutput = new ArrayList<Integer>();

Integer[] arr = {2, 2, 3, 5, 5, 5, 7, 9};

correctOutput.addAll(Arrays.asList(arr));

if (il.equals(correctOutput)) {

System.out.println("PASS output is correct");

} else {

System.out.println("FAIL output is not correct");

}

}

}

**MyBST.java**( Here is my Code below)**Here is the output from eclipse:**

PASS top() works on empty tree

PASS root node exists

PASS tree has BST property

PASS found value 9

FAIL returned true when searching for 6

PASS output is correctPASS top() works on empty tree

PASS root node exists

PASS tree has BST property

PASS found value 9

FAIL returned true when searching for 6

PASS output is correct

[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]

Campbell Ritchie

Sheriff

Posts: 48954

60

posted 8 years ago

I may have missed it, but I don't see an actual question. Remember, we are not here to do your work for you. people will bend over backwards to HELP you, but YOU have to do the work. Simply posting "here's my homework assignment" will annoy most people, who will then just ignore your post.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors