part c
package BST;
public class BinarySearchTree {
public static Node root;
public BinarySearchTree() { // Constructor
this.root = null;
}
public boolean search(int id) {
Node current = root;
while (current != null) {
if (current.key == id) {
return true;
} else if (current.key > id) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
/** The insert method was added
*
* @param id integer.
*/
public void insert(int id) {
Node newNode = new Node(id);
if (root == null) {
root = newNode;
return;
}
Node current = root;
Node parent = null;
while (true) {
parent = current;
if (id < current.key) {
current = current.left;
if (current == null) {
parent.left = newNode;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
private int HeightUtil(Node root) {
if (root == null)
return -1;
else
return 1 + Math.max(HeightUtil(root.left), HeightUtil(root.right));
}
public double height() { // Compute the height of Binary Search
return HeightUtil(root);
}
public void InorderTraversal() {
inOrderHelper(root);
}
private void inOrderHelper(Node root) {
if (root != null) {
inOrderHelper(root.left);
System.out.print(root.key + ” “);
inOrderHelper(root.right);
}
}
public Integer search_Next(Integer k)
{
if(root == null)
return null;
else
{
Node current = root;
while(current != null)
{
if(current.key == k) //found a matching key
{
//now go to the left most node in the right subtree
if(current.right == null) //there is right subtree?
return null;
else
{
current = current.right;
while(current.left != null) //no more left node?
{
current = current.left;
}
return current.key;
}
}
else if(k < current.key)
current = current.left;
else
current = current.right;
}
return null;//if no matching key was found
}
}
public static void main(String arg[]) {
Integer[] a = { 1, 5, 2, 7, 4 };
BinarySearchTree bst = new BinarySearchTree();
for (Integer n : a)
bst.insert(n);
bst.InorderTraversal();
System.out.println(“nsearch_Next(2) = “+bst.search_Next(2));
}
}
output
1 2 4 5 7
search_Next(2) = 4
part D
package BST;
import java.util.Random;
public class CompareHeights {
private static void generateAndCompare(int nodeSize)
{
Random numRandom=new Random();
Random signRandom = new Random();
BinarySearchTree bst = new BinarySearchTree();
int num,sign;
System.out.println(“Generating tree with “+nodeSize +” nodes”);
for(int i = 0; i < nodeSize; i++)
{
sign = signRandom.nextInt(2);
num = numRandom.nextInt(Integer.MAX_VALUE);
if(sign == 0)//whenever sign is 0 , make the number -ve
num = -num;
bst.insert(num);
}
System.out.println(“Generated tree , its height is “+bst.height());
double h = Math.log(nodeSize + 1 ) / Math.log(2); //calculating log base 2
System.out.println(“Expected minimum height of tree is log (” + (nodeSize+1) + “) = ” + h);
System.out.println(“—————“);
}
public static void main(String[] args) {
int n[] = {10, 100, 500, 1000, 2000, 5000, 10000, 100000, 1000000};
for(int i = 0; i<n.length; i++)
{
generateAndCompare(n[i]);
}
}
}
output
Generating tree with 10 nodes
Generated tree , its height is 6.0
Expected minimum height of tree is log (11) = 3.4594316186372978
—————
Generating tree with 100 nodes
Generated tree , its height is 13.0
Expected minimum height of tree is log (101) = 6.6582114827517955
—————
Generating tree with 500 nodes
Generated tree , its height is 20.0
Expected minimum height of tree is log (501) = 8.968666793195208
—————
Generating tree with 1000 nodes
Generated tree , its height is 19.0
Expected minimum height of tree is log (1001) = 9.967226258835993
—————
Generating tree with 2000 nodes
Generated tree , its height is 24.0
Expected minimum height of tree is log (2001) = 10.966505451905741
—————
Generating tree with 5000 nodes
Generated tree , its height is 30.0
Expected minimum height of tree is log (5001) = 12.288000889707574
—————
Generating tree with 10000 nodes
Generated tree , its height is 30.0
Expected minimum height of tree is log (10001) = 13.287856641840545
—————
Generating tree with 100000 nodes
Generated tree , its height is 39.0
Expected minimum height of tree is log (100001) = 16.60965490131509
—————
Generating tree with 1000000 nodes
Generated tree , its height is 47.0
Expected minimum height of tree is log (1000001) = 19.931570012018494
—————
part E
The minimum height of a BST with n nodes is log (n+1). So we see from the output above that the height of generated tree is atleast as much as log(n+1)
Here is my code for a and b !
