Question

IN JAVA!!

You may be working with a programming language that has arrays, but not nodes. In this case you will need to save your BST in a two dimensional array. In this lab you will write a program to create a BST modelled as a two-dimensional array. The output from your program will be a two-dimensional array.  

THEN: practice creating another array-based BST using integers of your choice.

Once you have figured out your algorithm you will be able to code it.

Use this input file which contains the number of integers (you will need this so you know how many rows you need) followed by the integers that are to put into the BST.

lab8.txt

10 50 40 45 25 80 90 60 13 52 70

In this input file the first number is 10. This is the number of nodes. So you will need a 10 x 3 array. However, I will test the program with different input so don't hard code in the 10. Pick up the first integer (say you call it n), you will then need to create an n x 3 array.

MY CODE

Lab8.java

import java.io.File;
import java.util.*;
import static labnumber8.Node.placement;
import static labnumber8.Node.print;
import static labnumber8.Node.twoDimensional;
//honestly have no idea why these needed to be imported, I made a seperate class
//for them but would only get error messages.
//the messages would disappear if I just imported them however.

public class LabNumber8 {
public static void main(String[] args) {
File file = new File("lab8.txt");
Scanner scnr = new Scanner(System.in);
int n = 0;
//to get the first input of the file
while(scnr.hasNext()) {
n = scnr.nextInt();
break;
}
//need to create an n x 3 array, in this case n is 10
int[][] arr = new int[n][3];
while(scnr.hasNext()) {
arr.add(scnr.nextInt());
}
//for whatever reason I cannot input any of the ints from the text file
//to the array, will continue to try but i have looked everywhere
//on stack overflow and nothing is making sense.
Node root = new Node(scnr.nextInt());
for(int i = 1; i < n; i++) {
root = placement(root, scnr.nextInt());
}
twoDimensional(root);
print(n);
}
}

Node.java
public class Node {
static int[][] arr;
int value;
Node right;
Node left;
Node(int value){
this.value = value;
right= null;
left = null;
}
  
//this method inserts each part of the BST in its correct spot
static Node placement(Node node, int val) {
if(node == null) {
return new Node(val);
}
if(val > node.value) {
node.right = placement(node.right, val);
}
else if(val < node.value) {
node.left = placement(node.left, val);
}
return node;
}

Answer 1

Last Updated: 21-04-2020

Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements.

Input:  Array {1, 2, 3}
Output: A Balanced BST
     2
   /  \
  1    3 

Input: Array {1, 2, 3, 4}
Output: A Balanced BST
      3
    /  \
   2    4
 /
1

Algorithm
BST from sorted Linked List. Constructing from sorted array in O(n) time is simpler as we can get the middle element in O(1) time. Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed.

1) Get the Middle of the array and make it root.
2) Recursively do same for left half and right half.
      a) Get the middle of left half and make it left child of the root
          created in step 1.
      b) Get the middle of right half and make it right child of the
          root created in step 1.

// Java program to print BST in given range

// 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[]{1, 2, 3, 4, 5, 6, 7};
       int n = arr.length;
       root = tree.sortedArrayToBST(arr, 0, n - 1);
       System.out.println("Preorder traversal of constructed BST");
       tree.preOrder(root);
   }
}

4 2 1 3 6 5 7 

Tree representation of above output:
     4  
 2      6
1  3  5   7

Time Complexity: O(n)
Following is the recurrance relation for sortedArrayToBST().

  T(n) = 2T(n/2) + C
  T(n) -->  Time taken for an array of size n
   C   -->  Constant (Finding middle of array and linking root to left 
                      and right subtrees take constant time)

def mergeSort(alist):

print("Splitting ",alist)

if len(alist)>1:

mid = len(alist)//2

lefthalf = alist[:mid]

righthalf = alist[mid:]

mergeSort(lefthalf)

mergeSort(righthalf)

fi=0

j=0

k=0

while i < len(lefthalf) and j < len(righthalf):

if lefthalf[i] <= righthalf[j]:

alist[k]=lefthalf[i]

                i=i+1

            else:

                alist[k]=righthalf[j]

                j=j+1

            k=k+1

        while i < len(lefthalf):

            alist[k]=lefthalf[i]

            i=i+1

            k=k+1

​

        while j < len(righthalf):

            alist[k]=righthalf[j]

            j=j+1

            k=k+1

    print("Merging ",alist)

​

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

​ Merg

  the length of the list is less than or equal to one, then we already have a sorted list and no more processing is necessary. It is important to note that the list may not have an even number of items. That does not matter, as the lengths will differ by at most one.

def mergeSort(alist):

    print("Splitting ",alist)

    if len(alist)>1:

        mid = len(alist)//

        lefthalf = alist[:mid]

        righthalf = alist[mid:]

        mergeSort(lefthalf)

        mergeSort(righthalf)

​

i=0

j=0

        k=0

        while i < len(lefthalf) and j < len(righthalf):

            if lefthalf[i] <= righthalf[j]:

                alist[k]=lefthalf[i]

                i=i+1

            else:

                alist[k]=righthalf[j]

                j=j+1

            k=k+1

        while i < len(lefthalf):

            alist[k]=lefthalf[i]

            i=i+1

            k=k+1

        while j < len(righthalf):

            alist[k]=righthalf[j]

            j=j+1

            k=k+1

    print("Merging ",alist)

​

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

​ Merg

def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

mergeSort(lefthalf)
mergeSort(righthalf)

i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] <= righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1

while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)