Question

2. Implement a main method that does the following: Use Java

(a) Creates a binary search tree to hold sports scores as data for a sport of your own choice

(b) Adds between 5 and 8 scores to the tree using standard tree operations Try insert

(c) Choose one of the tree traversals, preorder or postorder, and use it to print out all elements of the tree

(d) Delete one score from the tree using standard tree operations (suppose the score was found to be illegitimate) (e) Use an iterator to get a list for an inorder traversal for the tree (so that you can process each element from the tree), and print out a message about the sports score, including the sport and other informative information you can come up wit

Answer 1

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree { // can be made generic based on game type BinarySearchTree<? extends Game>

   public static void main(String[] args) {
       BinarySearchTree bst = new BinarySearchTree();

       bst.insertRecord(new Game("Cricket", 100, "India vs England"));
       bst.insertRecord(new Game("Cricket", 200, "India1 vs England1"));
       bst.insertRecord(new Game("Cricket", 99, "India2 vs England2"));

       bst.printTree();

       System.out.println("+++++++++++++++++++++++++++++++++++++++++++++");

       List<Game> list = new ArrayList<>();

       bst.inorderPopulateList(list);

       for (Game game : list) {
           System.out.println(game);
       }

       System.out.println("+++++++++++++++++++++++++++++++++++++++++++++");

       bst.deleteRecord(new Game("Cricket", 100, "India vs England"));

       bst.printTree();
   }

   private static class TreeNode {
       private Game game;
       private TreeNode left;
       private TreeNode right;

       public TreeNode(Game game) {
           this.game = game;
       }
   }

   TreeNode root;

   public TreeNode insertRecord(Game key) {
       return insertRecordUtil(this.root, key);
   }

   private TreeNode insertRecordUtil(TreeNode root, Game key) {

       if (root == null) {
           root = new TreeNode(key);
           this.root = root;
           return root;
       }

       if (key.getScore() < root.game.getScore())
           root.left = insertRecordUtil(root.left, key);
       else if (key.getScore() > root.game.getScore())
           root.right = insertRecordUtil(root.right, key);

       this.root = root;
       return root;
   }

   public TreeNode deleteRecord(Game key) {
       return deleteRecordUtil(root, key);
   }

   private TreeNode deleteRecordUtil(TreeNode root, Game key) {
       if (root == null) {
           return root;
       }

       if (key.getScore() < root.game.getScore()) {
           root.left = deleteRecordUtil(root.left, key);
       } else if (key.getScore() > root.game.getScore()) {
           root.right = deleteRecordUtil(root.right, key);
       } else {
           if (root.left == null)
               return root.right;
           else if (root.right == null)
               return root.left;

           root.game = minValue(root.right);

           root.right = deleteRecordUtil(root.right, root.game);
       }

       return root;
   }

   private Game minValue(TreeNode root) {
       Game minv = root.game;
       while (root.left != null) {
           minv = root.left.game;
           root = root.left;
       }
       return minv;
   }

   public void printTree() {
       printTree(this.root);
   }

   private void printTree(TreeNode root) {

       if (root == null) {
           return;
       }

       printTree(root.left);
       System.out.println(root.game.toString());
       printTree(root.right);
   }

   // Populates blank list by inorder traversal of bst
   public void inorderPopulateList(List<Game> list) {
       inorderPopulateListUtil(this.root, list);
   }

   private void inorderPopulateListUtil(TreeNode root, List<Game> list) {

       if (root == null) {
           return;
       }

       printTree(root.left);
       printTree(root.right);
       list.add(root.game);
   }

}

class Game { // can be abtract and derived classes like football, cricket etc can be used

   private String type;
   private Integer score;
   private String match; // A vs B

   // Add any attributes you can add

   public Game(String type, Integer score, String match) {
       this.type = type;
       this.match = match;
       this.score = score;
   }

   public String getType() {
       return type;
   }

   public void setType(String type) {
       this.type = type;
   }

   public Integer getScore() {
       return score;
   }

   public void setScore(Integer score) {
       this.score = score;
   }

   public String getMatch() {
       return match;
   }

   public void setMatch(String match) {
       this.match = match;
   }

   @Override
   public String toString() {

       return this.type + " Match : " + this.match + "With score " + this.score;
   }

}