Question

Write a program to use a binary search tree to store a list of computer games. Each node in the tree stores the title (string) of a computer game. Different games have different titles.
Your program should display the following menu repeatedly:
1. Insert new game
2. Search for games         
3. List games
4. quit
Option 1 should read a game (title) and add the game into the tree. 
Option 2 allows the user to enter a partial key (a prefix of key) and displays all the games whose titles match the partial key.
Option 3 list games using the breadth-first traversal. 

Answer 1

JAVA CODE:

import java.util.Queue;
import java.util.LinkedList;
import java.io.*;
class GameTree {
  
/* Class containing left and right child of current node and key value*/
class Node {
String key;
Node left, right;
  
public Node(String item) {
key = item;
left = right = null;
}
}
  
// Root of BST
Node root;
  
// Constructor
GameTree() {
root = null;
}
  
// This method mainly calls insertRec()
void insert(String key) {
root = insertRec(root, key);
}
  
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, String 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.compareTo(root.key)<0)
root.left = insertRec(root.left, key);
else if (key.compareTo(root.key)>0)
root.right = insertRec(root.right, key);
  
/* return the (unchanged) node pointer */
return root;
}

void GameSearch(String search){
SearchUtil(root,search);
}
  
void SearchUtil(Node root,String search) {
if (root != null) {
SearchUtil(root.left,search);
int length = search.length();
if(search.compareToIgnoreCase(root.key.substring(0,length))==0)
System.out.println(root.key);
SearchUtil(root.right,search);
}
}
void BFS()
{
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty())
{
Node tempNode = queue.poll();
System.out.println(tempNode.key + " ");
  
/*Enqueue left child */
if (tempNode.left != null) {
queue.add(tempNode.left);
}
  
/*Enqueue right child */
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
}
// Driver Program to test above functions
public static void main(String[] args)throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
GameTree tree = new GameTree();   
  
int choice;String name,search;
while(true){
System.out.println("1. Insert New Game");
System.out.println("2. Search For Games");
System.out.println("3. List Games");
System.out.println("4. Quit");
System.out.println("Enter Choice: ");
choice = Integer.parseInt(in.readLine());
if(choice == 4){
break;
}
switch(choice){
case 1:
System.out.println("Enter Name of the Game: ");
name = in.readLine();
tree.insert(name);
break;
case 2:
System.out.println("Enter Search String: ");
search = in.readLine();
System.out.println("Search Results:");
tree.GameSearch(search);
break;
case 3:
System.out.println("List of Games:");
tree.BFS();
System.out.println();
break;
}
  
}
}
}

OUTPUT: