Question

using java to write,show me the output. please write some common.

You CAN NOT use inbuild functions for Tree ADT operations.

using code below to finsih

3. Assume a BST considers the keys (integer) and no values. Here keys are stored in each node of the tree. Consider the following sequence in the given order. Write a program to create the binary search trees on the following sequences. i. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ii. 8, 12, 14, 10, 4, 6, 13, 11, 2, 5, 9, 1, 7, 3, 15 a) Print the above trees using Inorder traversal method that you implemented in question 2. b) Implement a search method for a BST. Check whether keys 15 and 25 are existing in the above BST or not. (your method can return Boolean value). c) Implement a delete method for a BST. I. Delete key 13 and print Inorder traversal of the BST after removal. II. Delete key 8 and print Inorder traversal of the BST after removal. d) Analyze and compare the performance (the worst and best-case) of above operations based on your implementation. (Submit a pdf document for this part)

public class Main
{
   public static void main(String[] args) {
       BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);
tree.root.left.right.left = new Node(10);
tree.root.left.right .right= new Node(11);
tree.root.right.left.right = new Node(12);
tree.root.right.left.left = new Node(13);
tree.root.right.right.left = new Node(14);
tree.root.right.right.right = new Node(15);
  
  
System.out.println("Preorder traversal of binary tree is ");
tree.printPreorder();
  
System.out.println("\nInorder traversal of binary tree is ");
tree.printInorder();
  
System.out.println("\nPostorder traversal of binary tree is ");
tree.printPostorder();
   }
}
class Node
{
int key;
Node left, right;
  
public Node(int item)
{
key = item;
left = right = null;
}
}
  
class BinaryTree
{
// Root of Binary Tree
Node root;
  
BinaryTree()
{
root = null;
}
  
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(Node node)
{
if (node == null)
return;
  
// first recur on left subtree
printPostorder(node.left);
  
// then recur on right subtree
printPostorder(node.right);
  
// now deal with the node
System.out.print(node.key + " ");
}
  
/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null)
return;
  
/* first recur on left child */
printInorder(node.left);
  
/* then print the data of node */
System.out.print(node.key + " ");
  
/* now recur on right child */
printInorder(node.right);
}
  
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(Node node)
{
if (node == null)
return;
  
/* first print data of node */
System.out.print(node.key + " ");
  
/* then recur on left sutree */
printPreorder(node.left);
  
/* now recur on right subtree */
printPreorder(node.right);
}
  
// Wrappers over above recursive functions
void printPostorder() { printPostorder(root); }
void printInorder() { printInorder(root); }
void printPreorder() { printPreorder(root); }
}

Answer 1

  
   //note: insertion deletion search takes o(n) time in worst case cmoplexity for a bst  
  
   public class Bst{
      
       class Node {
   int key;
   Node left, right;
  
   public Node(int item) {
   key = item;
   left = right = null;
   }
   }
  
   // Root of BST
   static Node root;
  
   // Constructor
   MyInvestment() {
   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);
   }
   }
  
   static boolean ifNodeExistsbool(int key) {
       boolean exists= ifNodeExists(root, key);
       return exists;
   }
   static boolean ifNodeExists(Node node, int key)
   {
   if (node == null)
   return false;
  
   if (node.key == key)
   return true;
  
   // then recur on left sutree /
   boolean res1 = ifNodeExists(node.left, key);
   if(res1) return true; // node found, no need to look further
  
   // node is not found in left, so recur on right subtree /
   boolean res2 = ifNodeExists(node.right, key);
  
   return res2;
   }
   void deleteKey(int key)
   {
   root = deleteRec(root, key);
   }
  
   /* A recursive function to insert a new key in BST */
   Node deleteRec(Node root, int key)
   {
   /* Base Case: If the tree is empty */
   if (root == null) return root;
  
   /* Otherwise, recur down the tree */
   if (key < root.key)
   root.left = deleteRec(root.left, key);
   else if (key > root.key)
   root.right = deleteRec(root.right, key);
  
   // if key is same as root's key, then This is the node
   // to be deleted
   else
   {
   // node with only one child or no child
   if (root.left == null)
   return root.right;
   else if (root.right == null)
   return root.left;
  
   // node with two children: Get the inorder successor (smallest
   // in the right subtree)
   root.key = minValue(root.right);
  
   // Delete the inorder successor
   root.right = deleteRec(root.right, root.key);
   }
  
   return root;
   }
   int minValue(Node root)
   {
   int minv = root.key;
   while (root.left != null)
   {
   minv = root.left.key;
   root = root.left;
   }
   return minv;
   }
  
      
           public static void main(String[] args) throws Exception {
               Bst tree = new Bst();
           tree.insert(1);
           tree.insert(2);
           tree.insert(3);
           tree.insert(4);
           tree.insert(5);
           tree.insert(6);
           tree.insert(7);
           tree.insert(8);
           tree.insert(9);
           tree.insert(10);
           tree.insert(11);
           tree.insert(12);
           tree.insert(13);
           tree.insert(14);
           tree.insert(15);
          
          
           tree.inorder();
           int key = 5;
          
           if (ifNodeExistsbool( key))
           System.out.println("YES");
           else
           System.out.println("NO");
          
           tree.deleteKey(13);
           System.out.println("Inorder traversal of the modified tree");
           tree.inorder();
          
           Bst tree1 = new Bst();
           tree1.insert(8);
           tree1.insert(12);
           tree1.insert(14);
           tree1.insert(10);
           tree1.insert(4);
           tree1.insert(6);
           tree1.insert(13);
           tree1.insert(11);
           tree1.insert(2);
           tree1.insert(5);
           tree1.insert(9);
           tree1.insert(1);
           tree1.insert(7);
           tree1.insert(3);
           tree1.insert(15);
          
           tree1.inorder();
           int key1 = 5;
          
           if (ifNodeExistsbool( key1))
           System.out.println("YES");
           else
           System.out.println("NO");
          
           tree1.deleteKey(8);
           System.out.println("Inorder traversal of the modified tree");
           tree1.inorder();
          
          
           }
          
           }