I have implemented a binary search tree. Most of my test in JUNIT test is going through, including these two. I have implementedleavesIsCorrectWhenTreeIsPerfect() and insertValuesInAscendingOrderIncrementsHeight().
Both of these test goes through, however i do not know if it is correctly written based on what their description is asking.
//EDIT: I have added a test that might be a help to one of the test a need help with.
//TODO: help me understand if I have written the correct code for the test in insertValuesInAscendingOrderIncrementsHeight() and leavesIsCorrectWhenTreeIsPerfect() based on what the description for the test is saying.
Have in mind, that I have not included all the tests in the test class, Because the goes through with my implementation of the tree.
Down here I have included my tree class and the test class with both the test I need help with.
/**
* An Binary Search tree implementation.
* @param <T>
*/
public class Tree <T extends Comparable <T>> implements BSTInterface <T>{
private int size;
private Node root;
public class Node{
private Node Left;
private Node Right;
private T data;
public Node(T data){
this.data = data;
}
public Node getRight(){
return Right;
}
public Node getLeft() {
return Left;
}
public T getData() {
return data;
}
}
public Tree (){
size = 0;
root = null;
}
/**
* Test for presence of a value.
* @param elem
* @return true/false
*/
@Override
public boolean search(T elem) {
if(root == null ||elem == null){
return false;
}
Node node = root;
while(true){
if(node.data.compareTo(elem) > 0){
if(node.Right == null){
return false;
} else{
node = node.Right;
}
} else if(node.data.compareTo(elem) == 0){
break;
} else{
if(node.Left== null){
return false;
}
else{
node = node.Left;
}
}
}
return true;
}
/**
* Add value to tree; duplicates are not allowed.
* Return true if the element is not already present (and is thus inserted),
* false otherwise.
*
* @param elem
* @return true/false
*/
@Override
public boolean insert(T elem) {
if (elem == null){
return false;
}
if (root == null){
root = new Node(elem);
size++;
return true;
}
Node node = root;
while (true){
if (node.data.compareTo(elem) > 0) {
if (node.Right == null){
node.Right = new Node(elem);
size++;
break;
} else {
node = node.Right;
}
} else if (node.data.compareTo(elem) == 0) {
return false;
} else {
if (node.Left == null){
node.Left = new Node(elem);
size++;
break;
} else {
node = node.Left;
}
}
}
return true;
}
/**
* the number of elements in the tree
* @return size.
*/
@Override
public int size() {
return size;
}
/**
* The height of the tree.
* The empty tree and the tree with only the root node both have height 0.
* @return the height of the tree.
*/
@Override
public int height() {
return countHeight(root);
}
/**
* Helper method for height
*/
private int countHeight(Node node){
if(node == null) {
return 0;
}
if (node.Left == null && node.Right == null) {
return 0;
}
return 1 + Math.max(countHeight(node.getLeft()), countHeight(node.getRight()));
}
/**
* The number of leaves in the tree.
* @return the amount of leaves the tree has.
*/
@Override
public int leaves() {
return countLeaves(root);
}
/**
* Helper method for leaves
*/
private int countLeaves(Node node) {
if (node == null) {
return 0;
}
if (node.Left == null && node.Right == null) {
return 1;
}
return countLeaves(node.Left) + countLeaves(node.Right);
}
/**
* A string describing the tree
* @return
*/
public String toString(){
String str = "[" + helpToString(root);
if (str.length() > 1) {
str = str.substring(0, str.length() - 2);
} return str + "]";
}
/**
* Helper method for toString
*/
private String helpToString(Node node) {
String str = "";
if (node != null) {
str += helpToString(node.Right);
str += node.data + ", ";
str += helpToString(node.Left);
}
return str;
}
}
import org.junit.Test;
import org.junit.Before;
import org.junit.Rule;
import org.junit.rules.Timeout;
import static org.junit.Assert.*;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.CoreMatchers.*;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* Test class for a tree.
*/
public class TreeTest{
@Rule public Timeout globalTimeout = Timeout.seconds(5);
Tree<Integer> tree;
int[] elementsInTree;
int[] elementsNotInTree;
@Before
public void setUp() {
/**
* This tree should look like this:
*
* 8
* /
* 3 10
* /
* 1 6 14
* / /
* 4 7 13
*/
tree = new Tree<>();
elementsInTree = new int[] {8, 10, 14, 13, 3, 1, 6, 4, 7};
for (int elem : elementsInTree) {
tree.insert(elem);
}
elementsNotInTree = new int[] {34, -3, -10, 12, 74, 5};
}
@Test
public void heightIsLogOfNumLeavesTreeIsPerfect() {
// For a perfect tree, tree.height() == log2(tree.leaves()
// Arrange
Tree<Integer> tree = new Tree<>();
int[] elements = new int[] {8, 3, 10, 1, 6, 9, 14};
int numLeaves = 4;
int logNumLeaves = (int) Math.round(Math.log(numLeaves) / Math.log(2));
for (int elem : elements) {
tree.insert(elem);
}
// Act
int height = tree.height();
// Assert
assertThat(height, equalTo(logNumLeaves));
}
@Test
public void leavesIsCorrectWhenTreeIsPerfect() { //TEST
// A perfect tree has all leaves at the same depth, and all internal nodes
// (i.e. non-leaves) have two children
//
// This test should assert that a perfect tree with 2*n-1 nodes total,
// has exactly n leaves (i.e. that Tree.leaves() returns n).
//
// An example is the perfect three-node tree from the test above:
//
// (1338)
// /
// (1337) (1396)
// You have to construct your own tree here, with n >= 4
Tree <Integer> tree = new Tree<>();
int n = 4;
for(int i = 0; i>=n; i++) {
tree.insert(i);
int numLeaves = 2*n-1;
int leaves = tree.leaves();
assertThat(leaves,equalTo(numLeaves));
}
}
// Tests for insert/height
@Test
public void insertValuesInAscendingOrderIncrementsHeight() { //TEST
// When inserting elements in ascending order, each element is inserted
// to the right of the deepest node, so the height should increment by
// 1 for each element inserted.
Tree <Integer> tree = new Tree<>();
int val = 100;
for(int i = 0; i < val; i++){
tree.insert(i);
}
int treeHeight = tree.height();
treeHeight++;
assertThat(tree.size(),equalTo(treeHeight));
}
}
Advertisement
Answer
It’s awkward that “n” is used in the instructions to describe a tree with n leaves because “n” is traditionally used to describe your node count. But picture a tree with 4 nodes at the bottom, then half that for the prior layer, then half again for the first layer, and you have a tree with 1+2+4 nodes, or 7 nodes total, which coincides with the formula 2*n-1 (2*4-1=7).
@Test
public void leavesIsCorrectWhenTreeIsPerfect() {
int n=4;
int[] balanced=new int[] {4,2,6,1,3,5,7};
for (int i=0; i<balanced.length; i++) {
tree.insert(balanced[i]);
}
int leaves = tree.leaves();
assertThat(balanced.length,equalTo(2*n-1));
assertThat(leaves,equalTo(n));
}