Question

Assignment on Java programing
1. Write programs for the following exercises in Java. Each file should have short description of the implemented class and for files with main method the problem it is solving. Make sure your files have appropriate names. Programs should write output to the Console.

b) BST: Implement Binary Search Tree ADT with insert(int key), delete(int key), Node find(int key), and in-order traverse() where it prints the value of the key. Your operations should use recursion. The tree should store key as integer. You should have a single file with class BST for the program. Your test program (main method) should demonstrate that all operations work correctly. Note that your textbook has the pseudo code and code in C for these operations that you can use but you need to modify a little to meet the assignment instructions and grading criteria.

c) BST2List: Copy your BST implementation from above and call it BST2. Change the Node to have additional data: status of type boolean and change BST2 operations appropriately: insert(int key, boolean status), delete(int key), find(int key), traverse(). Then implement an algorithm as method, findList(int low, int max) in BST2 class which prints out all key values within the range low and max if the status is true. Write test program which creates a BST2 instance and loads with below data, displays the values of the nodes in the tree in-order, displays low and max values, and calls findList to display values in range. Evaluate and report the time and space complexity of your findList algorithm.
For example,

Original list with status values:

45 false, 38 true, 21 false, 40 true, 50 true, 86 true, 90 false
In-order traversal of the BST: 21 38 40 45 50 86 90
low=39
max=51
Find list: 40 50

Grading Rubric
Points Criteria
10 Programs use object oriented program approach, have the appropriate naming convention, author’s name, and brief description of the implementation in the files
and the problem it is solving for main() methods
30 InsertionSort:
Correctly implements raw array for data Correctly implements insertion sort algorithm that was covered in class.Correctly selects test data for the analysis and describes in the report Correctly analyzes the runtime performance of the sort, provides results and conclusions in the report
explains implementation of insertion sort using raw array
explains test data used, analysis, and results of sort performance
shows the running program for given instance problem and explains
output
For extra credit: manually show the array contents after each iteration of the sort and explain what it is doing
30 BST:
Correctly implements Binary Search Tree ADT with insert, delete, find, and in-order traverse where it prints the value of the node.
explains implementation of BST ADT, test program, shows program running, and explains output
30 BST2List:
Correctly adds findList method to modified BST2 ADT
Correctly implements algorithm (implemented as method) with recursion to
print all the nodes with values in the range of low and max inclusive when
status=true
Test program creates a BST2 and loads with data

Answer 1

Searching a key // A utility function to search a given key in BST public Node search(Node root, int key) {     // Base Cases: root is null or key is present at root     if (root==null || root.key==key)         return root;     // val is greater than root's key     if (root.key > key)         return search(root.left, key);     // val is less than root's key     return search(root.right, key); } Insertion of a key // Java program to demonstrate insert operation in binary search tree class BinarySearchTree { /* Class containing left and right child of current node and key value*/ class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } // Root of BST Node root; // Constructor BinarySearchTree() { root = null; } // This method mainly calls insertRec() void insert(int key) { root = insertRec(root, key); } /* A recursive function to insert a new key in BST */ Node insertRec(Node root, int key) { /* If the tree is empty, return a new node */ if (root == null) { root = new Node(key); return root; } /* Otherwise, recur down the tree */ if (key < root.key) root.left = insertRec(root.left, key); else if (key > root.key) root.right = insertRec(root.right, key); /* return the (unchanged) node pointer */ return root; } // This method mainly calls InorderRec() void inorder() { inorderRec(root); } // A utility function to do inorder traversal of BST void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.println(root.key); inorderRec(root.right); } } // Driver Program to test above functions public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); // print inorder traversal of the BST tree.inorder(); } } // This code is contributed by Ankur Narain Verma Output : 20 30 40 50 60 70 80

// Java program to correct the BST
// if two nodes are swapped
import java.util.*;
import java.lang.*;
import java.io.*;

class Node {

int data;
Node left, right;

Node(int d) {
data = d;
left = right = null;
}
}

class BinaryTree
{
Node first, middle, last, prev;

// This function does inorder traversal
// to find out the two swapped nodes.
// It sets three pointers, first, middle
// and last. If the swapped nodes are
// adjacent to each other, then first
// and middle contain the resultant nodes
// Else, first and last contain the
// resultant nodes
void correctBSTUtil( Node root)
{
if( root != null )
{
// Recur for the left subtree
correctBSTUtil( root.left);

// If this node is smaller than
// the previous node, it's
// violating the BST rule.
if (prev != null && root.data <
prev.data)
{
// If this is first violation,
// mark these two nodes as
// 'first' and 'middle'
if (first == null)
{
first = prev;
middle = root;
}

// If this is second violation,
// mark this node as last
else
last = root;
}

// Mark this node as previous
prev = root;

// Recur for the right subtree
correctBSTUtil( root.right);
}
}

// A function to fix a given BST where
// two nodes are swapped. This function
// uses correctBSTUtil() to find out
// two nodes and swaps the nodes to
// fix the BST
void correctBST( Node root )
{
// Initialize pointers needed
// for correctBSTUtil()
first = middle = last = prev = null;

// Set the poiters to find out
// two nodes
correctBSTUtil( root );

// Fix (or correct) the tree
if( first != null && last != null )
{
int temp = first.data;
first.data = last.data;
last.data = temp;
}
// Adjacent nodes swapped
else if( first != null && middle !=
null )
{
int temp = first.data;
first.data = middle.data;
middle.data = temp;
}

// else nodes have not been swapped,
// passed tree is really BST.
}

/* A utility function to print
Inoder traversal */
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(" " + node.data);
printInorder(node.right);
}


// Driver program to test above functions
public static void main (String[] args)
{
/* 6
/ \
10 2
/ \ / \
1 3 7 12

10 and 2 are swapped
*/

Node root = new Node(6);
root.left = new Node(10);
root.right = new Node(2);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.right = new Node(12);
root.right.left = new Node(7);

System.out.println("Inorder Traversal"+
" of the original tree");
BinaryTree tree = new BinaryTree();
tree.printInorder(root);

tree.correctBST(root);

System.out.println("\nInorder Traversal"+
" of the fixed tree");
tree.printInorder(root);
}
}