Question

Write a program to do the following. JAVA CODE • Input an integer n. • Create...

Write a program to do the following. JAVA CODE

• Input an integer n.

• Create a BinarySearchTree S inserting the keys 1, 2, . . . , n in that order, which will result in a completely-skewed tree.

• Measure the time to search for n + 1 in S. 4

• Display the time taken for search.

Homework Answers

Answer #1

If you like the solution please give it a thumbs up !

Java Code :-

import java.io.*;
import java.util.Scanner;
class BST { 

        // Node class representing node of binary search tree
        class Node { 
                int key; 
                Node left, right; 

                public Node(int item) { 
                        key = item; 
                        left = right = null; 
                } 
        } 

        Node root; 

        BST() { 
                root = null; 
        } 

        void insert(int key) { 
        root = insertHelper(root, key); 
        } 
        
        // A recursive function to insert a new key in BST 
        Node insertHelper(Node root, int key) { 

                // If the tree is empty, return a new node 
                if (root == null) { 
                        root = new Node(key); 
                        return root; 
                } 

                // else recur of left and right subtree
                if (key < root.key) 
                        root.left = insertHelper(root.left, key); 
                else if (key > root.key) 
                        root.right = insertHelper(root.right, key); 

                return root; 
        } 
        
        // function to search for key in BST
        boolean search(int key)
        {
                return searchHelper(root,key);
        }
        boolean searchHelper(Node root, int key) 
        { 
            // Base Cases 
            if (root==null) 
                return false;
            if(root.key == key)
                return true;
          
            if (root.key > key) 
                return searchHelper(root.left, key); 
          
            return searchHelper(root.right, key); 
        } 


        public static void main(String[] args) { 
                Scanner sc = new Scanner(System.in);

                BST tree = new BST(); 
                
                System.out.println("Enter the value for integer n :-");
                
                int n = sc.nextInt();
                
                for(int i=1;i<=n;i++)
                        tree.insert(i);
                
                // measure system time before calling search function
                long start = System.nanoTime(); 
                
                boolean find = tree.search(n+1);
                
                // measure system time after calling search function
                long end = System.nanoTime(); 
                
                System.out.println("Time taken for search :- " + (end - start) + "ns (nano seconds)"); 

        } 
} 

Sample Input :-

Enter the value for integer n :-

50

Sample Output :-

Time taken for search :- 11108ns (nano seconds)

Sample Input :-

Enter the value for integer n :-

10000

Sample Output :-

Time taken for search :- 1621465ns (nano seconds)
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Write a program to do the following. • Input an integer n. • Create a BinarySearchTree...
Write a program to do the following. • Input an integer n. • Create a BinarySearchTree B containing the same items, but inserting them in an order that will yield the tree balanced. The following algorithm, known as pre-order traversal, gives you a strategy to produce that sequence. seq(low, high, T){ if (low <= high){ mid = (low+high)/2 T.insert(mid) seq(low, mid-1, T) seq(mid+1, high, T) } } • Measure the time to search for n + 1 in B. •...
Write a program that does the following. *Java Code* • Create an instance of the Hashtable...
Write a program that does the following. *Java Code* • Create an instance of the Hashtable class from the Java API • Make the initial table size of the hash table 1000 and the load factor 0.75 (which has been shown experimentally to be optimal). • Create an instance of the AVLtree class attached to this homework. • Measure the running time of adding various numbers of entries (as required by the table below) to the hash table and the...
Binary Search Tree Code in Java Write a program that prompts user to enter however many...
Binary Search Tree Code in Java Write a program that prompts user to enter however many numbers they want to add to the binary search tree. Then have the user input numbers until the tree contains that many elements. If the user enters a number that already exists in the tree, then a message should be displayed "Number is already in the tree". Once all elements are added to the tree print its contents in sorted order. Assume all user...
5) Create a Java program using Scanner: Write a program where you will enter the grade...
5) Create a Java program using Scanner: Write a program where you will enter the grade score for 5 classes, then it will display total points and average and it will display the grade based on percentage. Steps: 1) Declare variable integer for English, Chemistry, Java Programming, Physics and Math 2) Declare variable total and percentage 3) Create Scanner object and prompt the user to enter grades for each class and input grades after each class 4) Calculate total of...
Write a program to allow user to create a binary search tree. Your program should display...
Write a program to allow user to create a binary search tree. Your program should display in BFT and DFT(in order) format.
Write a java program to display a given range of integer numbers (0 to 9) in...
Write a java program to display a given range of integer numbers (0 to 9) in the following order: Example : given (5 to 9), the program displays 56789 67895 78956 89567 95678 The first line displays the min to max range. Each line that follows should display the next higher number except when it hits the maximum number. In that situation, the line wraps back to the minimum sequence. For this problem write a static method to do the...
Write a Java program using the OOP paradigm to do the following: 1. Main Function: create...
Write a Java program using the OOP paradigm to do the following: 1. Main Function: create a list with a million items, and you can use the generate function to add a million random values to the list. 2. Create a method to sort the list created in the main function using bubble sort, then use the sorted list to search for the (k) value using binary search. 3. Create a method to create a new list of 1000 items...
Please write a java program Instructions Your goal is to take N integer inputs from the...
Please write a java program Instructions Your goal is to take N integer inputs from the user -- N's value will be given by the user as well. You can assume the user provides a valid value for N, i.e., >0. Store the input integers in an array of size N in the order they are provided. These tasks should be done in the main() method. Create a new method called checkArray() that will take the previously created array as...
Write a script to display numbers from 1 to n, where n is an integer provided...
Write a script to display numbers from 1 to n, where n is an integer provided by users (if not, default to 10). Hint: use “read” command to accept user input. a) Display the source code in an editor (#4-9) b) Execute your script in the terminal, and display the command and the result (#4-10)
A. Write a Java program that asks the user to enter “bus” or “subway” or “walk”....
A. Write a Java program that asks the user to enter “bus” or “subway” or “walk”. If the user enters “bus” display “$1.00”. If they enter “subway” display “$1.50 and if they enter “walk” display “Free”. B. Write a java program that creates the following two arrays: String[] candidates = {“S Jones”,”Justin Fairfax”,”Clark Duncan”}; int[] votes = {7345,4324,3211}; Write the code that will search the votes array for the candidate with the largest number of votes and prints the name...