Question
Test Java Cases:
Goal Write a Java program using Binary Search Trees. BST Heights A Binary Search Tree is a tree where, for every node the values in its left branch are lower that the node's value, and the values in its right branch are higher than the node's value (see figure below). BST like the one in the figure are built by adding a sequence of numbers into an empty tree. In this case, the sequence "10 5 1 12 14 6" is one such sequence that results in the tree shown. In this assignment, you will build trees given different sequence of numbers and will identify the sequence that generates the tree with the lowest height. To this end, write a class "Program 1" the implements the following method: public static String lowestHeight(String[] sequences) This method receives an array of strings, where each string is a sequence of positive numbers, and returns the string sequence that results in the tree with the minimum height. For example, the array {"1 2 3", "3 1 2", "2 1 3", "2 3 1"} has 4 sequences (which just by chance have the same number of elements). These sequences result in the trees below. Note that that the sequences "2 1 3" and "2 3 1" result in the same tree, which in this case is the one with minimum height. When there is a tie among minimum height trees your program should choose the sequence where smaller numbers come first. In this case, "2 13" has a smaller starting sequence than "2 3 1" (i.e., "2 1" vs. "2 3") and as such it is the chosen solution. import static org.junit.Assert.*; import org.junit.Test; public class Program1Test { @Test public void test0() { String[] array -{"12 3", "3 1 2", "2 1 3", "2 3 1" }; String actual = Program1.lowestHeight( array ); String expected = "2 1 3"; assertEquals( "Incorrect result", expected, actual ); } @Test public void test1() { String[] array = { "3", "2", "5" }; String actual = Program1.lowestHeight( array ); String expected = "2"; assertEquals( "Incorrect result", expected, actual ); } @Test public void test2() { String[] array = {"4 2 1 6 7 3 5", "4 2 3" }; String actual = Program1.lowestHeight( array ); String expected = "4 2 1 6 7 3 5"; assertEquals( "Incorrect result", expected, actual ); } @Test public void test3() { String[] array = {"4 2 3", "2 4 3", "5 4 1", "7 8 6", "1 4 5" }; String actual = Program1.lowestHeight( array ); String expected = "7 8 6"; assertEquals( "Incorrect result", expected, actual ); } @Test public void test4() { String[] array -{"1 9 5 7 6", "8 12 14 16 18", "8 12 10 11 9 14 15 13 4 2 6 1 3 5 7", "5 4 3 2 1" }; String actual = Program1.lowestHeight( array ); String expected = "8 12 10 11 9 14 15 13 4 2 6 1 3 5 7"; assertEquals( "Incorrect result", expected, actual ); } @Test public void test5() { String[] array = {"4 8 6 5 9", "4 8 6 5 7 9", "4 8 6 5 7", "4 8 6 7" }; String actual = Program1.lowestHeight( array ); String expected = "4 8 6 5 7"; assertEquals( "Incorrect result", expected, actual ); } }
Explanation / Answer
Binary Search Tree Example public class BinaryTreeExample {public static void main(String[] args) {new BinaryTreeExample().run(); }static class Node { Node left; Node right;int value;public Node(int value) {this.value = value; } }public void run() { Node rootnode = new Node(25); System.out.println("Building tree with rootvalue " + rootnode.value); System.out.println("======================= =========="); insert(rootnode, 11); insert(rootnode, 15); insert(rootnode, 16); insert(rootnode, 23); insert(rootnode, 79); System.out.println("Traversing tree in order"); System.out.println("======================== ========="); printInOrder(rootnode); }public void insert(Node node, int value) {if (value node.value) {if (node.right != null) { insert(node.right, value); } else { System.out.println(" Inserted " + value + " to right of node " + node.value); node.right = new Node(value); } } }public void printInOrder(Node node) {if (node != null) { printInOrder(node.left); System.out.println(" Traversed " + node.value); printInOrder(node.right); } }}Output of the program Building tree with root value 25 ================================= Inserted 11 to left of node 25 Inserted 15 to right of node 11 Inserted 16 to right of node 15 Inserted 23 to right of node 16 Inserted 79 to right of node 25 Traversing tree in order ================================= Traversed 11 Traversed 15 Traversed 16 Traversed 23 Traversed 25 Traversed 79
