Question

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.

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)