Write the Java source code necessary to build a solution for the problem below:

Question

Write the Java source code necessary to build a solution for the problem below: You are about to start a new "Thank You Note" service and you are seeking a way to store the names of the people to whom the notes must be sent in a way that reflects the order that the gifts arrived. You searched the web and found that storing things in a binary tree is a very efficient way to do this so you begin to experiment. To explore the possibilities, you create a binary search tree and make an attempt to store the names as you think they should be stored. To test the search scheme that best reflects the order of the gifts arrival, you store the names of the sender and then do three searches to determine the best match. Remember, you have put the names in the list that is stored in the tree in the order in which they arrived. Which tree traversal algorithm best matches the list that you want to print? To solve the problem, create a binary search tree from an array of the following names: Daniel, George, Adam, Peter, Michael, Jones, Tom, Allison, James, and Brian. Perform a preorder, inorder and postorder traversal on the binary tree and print the names in the order of the traversal. Remove Peter and Brian from the tree and perform the traversal again. Please provide a working code that will run. Thank you.

Explanation / Answer

class BinarySearchTree
{
/* 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
BinarySearchTree()
{
root = null;
}

// This method mainly calls deleteRec()
void deleteKey(String key)
{
root = deleteRec(root, key);
}

/* A recursive function to delete key in BST */
Node deleteRec(Node root, String key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;

/* Otherwise, recur down the tree */
if (key.compareTo(root.key) < 0)
root.left = deleteRec(root.left, key);
else if (key.compareTo(root.key) > 0)
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;
}

String minValue(Node root)
{
String minv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}

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 inorder()
{
inorderRec(root);
System.out.println();
}

// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}

void preorder()
{
preorderRec(root);
System.out.println();
}

// A utility function to do preorder traversal of BST
void preorderRec(Node root)
{
if (root != null)
{
   System.out.print(root.key + " ");
preorderRec(root.left);
preorderRec(root.right);
}
}
  
void postorder()
{
postorderRec(root);
System.out.println();
}

// A utility function to do preorder traversal of BST
void postorderRec(Node root)
{
if (root != null)
{
postorderRec(root.left);
postorderRec(root.right);
   System.out.print(root.key + " ");
}
}
  
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();

tree.insert("Daniel");
tree.insert("George");
tree.insert("Adam");
tree.insert("Peter");
tree.insert("Michael");
tree.insert("Jones");
tree.insert("Tom");
tree.insert("Allison");
tree.insert("James");
tree.insert("Brian");

System.out.println("Inorder traversal of the given tree");
tree.inorder();
  
System.out.println("Preorder traversal of the given tree");
tree.preorder();
  
System.out.println("Postorder traversal of the given tree");
tree.postorder();
  
tree.deleteKey("Peter");
tree.deleteKey("Brian");
System.out.println("Traversals after removal");
  
System.out.println("Inorder traversal of the given tree");
tree.inorder();
  
System.out.println("Preorder traversal of the given tree");
tree.preorder();
  
System.out.println("Postorder traversal of the given tree");
tree.postorder();
}
}

// Sample output

Inorder traversal of the given tree
Adam Allison Brian Daniel George James Jones Michael Peter Tom
Preorder traversal of the given tree
Daniel Adam Allison Brian George Peter Michael Jones James Tom
Postorder traversal of the given tree
Brian Allison Adam James Jones Michael Tom Peter George Daniel
Traversals after removal
Inorder traversal of the given tree
Adam Allison Daniel George James Jones Michael Tom
Preorder traversal of the given tree
Daniel Adam Allison George Tom Michael Jones James
Postorder traversal of the given tree
Allison Adam James Jones Michael Tom George Daniel

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.