1 Generate 50 random numbers ranging from 1 to 99 and store

1. Generate 50 random numbers ranging from 1 to 99 and store it in an array (DO NOT SORT THE ARRAY). Print these values to the screen.

2. Now take one number at a time sequentially starting from the leftmost value (the value at index position 0 of the array) and insert it into a Binary Search Tree.

3. You can use a second array to store the Binary Search Tree - use the formula discussed in class to store Left Child and Right Child.

4. Upon building the Binary Search Tree, follow the rule that LeftChild < Parent <= RightChild.

5. Print out the values of this second array. 6. Compare the original distribution of the values in the array vs the distribution after creating the Binary Search Tree (the second array/ArrayList) by printing this observation/comparison to the screen.

Solution

// Java program to Compare 50 Random numbers vs BST with Random Numbers
import java.util.Random;
// A binary tree node
class Node {
  
   int data;
   Node left, right;
  
   Node(int d) {
       data = d;
       left = right = null;
   }
}

class BinaryTree {
  
   static Node root;

   /* A function that constructs Balanced Binary Search Tree
   from a sorted array */
   Node sortedArrayToBST(int arr[], int start, int end) {

       /* Base Case */
       if (start > end) {
           return null;
       }

       /* Get the middle element and make it root */
       int mid = (start + end) / 2;
       Node node = new Node(arr[mid]);

       /* Recursively construct the left subtree and make it
       left child of root */
       node.left = sortedArrayToBST(arr, start, mid - 1);

       /* Recursively construct the right subtree and make it
       right child of root */
       node.right = sortedArrayToBST(arr, mid + 1, end);
      
       return node;
   }

   /* A utility function to print preorder traversal of BST */
   void preOrder(Node node) {
       if (node == null) {
           return;
       }
       System.out.print(node.data + \" \");
       preOrder(node.left);
       preOrder(node.right);
   }
  
   public static void main(String[] args) {
       BinaryTree tree = new BinaryTree();
       int[] arr = new int[50];

       Random r = new Random();               //Random Class object creation
       int Low = 1;                           //low value
       int High = 99;                           //define high value
       System.out.println(\"Random 50 Elements : \ \");  
       for(int i=0;i<50;i++)                                   //loop to create 50 random numbers
       {
       arr[i] = r.nextInt(High-Low) + Low;
      
       System.out.print(arr[i]+\" \");                       //Display random numbers
       }
  
       int n = arr.length;
       root = tree.sortedArrayToBST(arr, 0, n - 1); //array elements converted to bst with left,root,right constraint
       System.out.println(\"\ BST(left,root,right) : \ \");
       tree.preOrder(root);                                   //Dispaly BST tree
   }
}

OutPut :

Random 50 Elements :

54 56 42 1 50 40 59 85 30 56 73 50 37 18 39 81 92 61 37 6 9 21 96 90 43 57 95 66 65 73 47 20 27 60 60 95 94 63 65 79 29 25 15 74 64 48 84 63 13 40

BST(left,root,right) :

43 50 40 42 54 56 1 50 30 59 85 56 73 61 39 37 18 81 92 9 37 6 96 21 90 63 47 66 57 95 65 73 60 20 27 95 60 94 74 29 65 79 25 15 84 64 48 13 63 40