
Program Plan:
- Include the required import statement.
- Define the main class.
- Define the main method using public static main.
- Allocate memory to the class “Test”.
- Define the “Test” class.
- Declare the object for the BST.
- Display the initial height of the tree.
- Get the input string from the user.
- Display the height of the tree.
- Call the “breathFirstTraversal” method.
- Create an object and set the string values to that object.
- Again call the “breathFirstTraversal” method.
- Create an integer object for class and set the integer values to that object.
- Display the results.
- Define the “BST” class.
- Declare the required variables.
- Create a default BST class.
- Create a binary tree from an array of objects.
- The “height” method will return the height of the tree.
- Define “breathFirstTraversal” method.
- Declare the linked list.
- Add the values to the list.
- If the list is not empty print the elements.
- If the left node is not null, add the value to the left subtree.
- If the right node is not null, add the value to the right subtree.
- Define the “search” method.
- Start the traverse from the root of the tree.
- If the search element is in the left subtree set that value in “current” variable otherwise set the “current” variable as right subtree value.
- Define the “insert” method.
- If the root is null create the tree otherwise insert the value into left or right subtree.
- Define the “createNewNode”
- Return the result of new node creations.
- Define the “inorder”
- Inorder traverse from the root.
- Define the protected “inorder” method
- Traverse the tree according to the inorder traversal concept.
- Define the “postorder”
- Postorder traverse from the root.
- Define the protected “postorder” method
- Traverse the tree according to the postorder traversal concept.
- Define the “preorder”
- Preorder traverse from the root.
- Define the protected “preorder” method
- Traverse the tree according to the preorder traversal concept.
- Define the “TreeNode” class
- Declare the required variables.
- Define the constructor.
- Define the “getSize” method.
- Return the size.
- Define the “getRoot” method
- Return the root.
- Define the “java.util.ArrayList” method.
- Create an object for the array list.
- If the “current” is not equal to null, add the value to the list.
- If the “current” is less than 0, set the “current” as left subtree element otherwise set the “current” as right subtree element.
- Return the list.
- Define the “delete” method.
- If the “current” is not equal to null, add the value to the list.
- If the “current” is less than 0, delete the “current” as left subtree element otherwise delete the “current” as right subtree element.
- Return the list.
- Define the “iterator” method.
- Call the “inorderIterator” and return the value.
- Define the “inorderIterator”
- Create an object for that method and return the value
- Define the “inorderIterator” class.
- Declare the variables.
- Define the constructor.
- Call the “inorder” method.
- Define the “inorder” method.
- Call the inner “inorder” method with the argument.
- Define the TreeNode “inorder” method.
- If the root value is null return the value, otherwise add the value into the list.
- Define the “hasNext” method
- If the “current” value is less than size of the list return true otherwise return false.
- Define the “next” method
- Return the list.
- Define the “remove” method.
- Call the delete method.
- Clear the list then call the “inorder” method.
- Define the “clear” method
- Set the values to the variables
- Define the interface.
- Declare the required methods.
- Define the required methods.
- Define the main method using public static main.

The below program will add the “breathFirstTraversal” method in the given BST class as follows:
Explanation of Solution
Program:
//import statement
import java.util.*;
//class Test
public class Test
{
// main method
public static void main(String[] args)
{
//allocation of memory
new Test();
}
//definition of "Test"
public Test()
{
//declaration an object of BST
BST<String> tree = new BST<>();
//get the input from the user
System.out.print("The height of tree is " + tree.height());
Scanner input = new Scanner(System.in);
//print the statement
System.out.print("\nEnter strings: ");
//check the condition
for (int i = 0; i < 6; i++)
{
//get the input from the user
String s = input.next();
//insert the value
tree.insert(s.trim());
}
//get the input from the user
System.out.print("\nThe height of tree is " + tree.height());
//insert the value to the tree
tree.insert("Green");
//get the input from the user
System.out.print("\nThe height of tree is " + tree.height());
//print the new line
System.out.println();
//call the "breadthFirstTraversal" method
tree.breadthFirstTraversal();
//create the object for the BST
BST<String> tree1 = new BST<>(new String[]
{"Tom", "George", "Jean", "Jane", "Kevin", "Peter", "Susan",
"Jen", "Kim", "Michael", "Michelle"});
//print the statement
System.out.print("\nThe breadth-first traversal is ");
//call the "breadthFirstTraversal" method
tree1.breadthFirstTraversal();
//get the input from the user
System.out.print("\nThe height of tree1 is " + tree1.height());
//create the object for the BST
BST<Integer> tree2 =
new BST<>(new Integer[]{50, 45, 35, 48, 59, 51, 58});
//print the statement
System.out.print("\nThe breadth-first traversal for tree2 is ");
//call the "breadthFirstTraversal" method
tree2.breadthFirstTraversal();
//get the input from the user
System.out.print("\nThe height of tree2 is " + tree2.height());
}
//definition of "BST" class
public class BST<E extends Comparable<E>> implements Tree<E>
{
//declare the variables
protected TreeNode<E> root;
protected int size = 0;
//create a default binary tree
public BST()
{
}
//create a binary tree from an array of objects
public BST(E[] objects)
{
//check the condition
for (int i = 0; i < objects.length; i++)
//insert the values
insert(objects[i]);
}
// definition of "height"
public int height()
{
//returns the height of this binary tree
return height(root);
}
// definition of "height"
private int height(TreeNode root)
{
//check the condition
if (root == null)
{
//return the value
return -1;
}
else
{
//return the value
return 1 + Math.max(height(root.left), height(root.right));
}
}
// definition of "breadthFirstTraversal" method
public void breadthFirstTraversal()
{
//declaration of linked list
java.util.LinkedList <TreeNode<E>> queue =
new java.util.LinkedList<TreeNode<E>>();
//check the condition
if (root == null)
//return statement
return;
//add the value to the queue
queue.add(root);
//check the condition
while (!queue.isEmpty())
{
//declaration of variable
TreeNode<E> node = queue.removeFirst();
//print the statement
System.out.print (node.element + " ");
//check the condition
if (node.left != null)
//add the value to the queue
queue.add(node.left);
//check the condition
if (node.right != null)
//add the value to the queue
queue.add(node.right);
}
}
//definition of "search" method
public boolean search(E e)
{
//start from the root
TreeNode<E> current = root;
//check the condition
while (current != null)
{
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
current = current.left;
}
//check the condition
else if (e.compareTo(current.element) > 0)
{
//set the value
current = current.right;
}
//otherwise
else
//return statement
return true;
}
//return statement
return false;
}
//definition of "insert" method
public boolean insert(E e)
{
//check the condition
if (root == null)
//create a new root
root = createNewNode(e);
//otherwise
else
{
// locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
//check the condition
while (current != null)
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
parent = current;
current = current.left;
}
//check the condition
else if (e.compareTo (current.element) > 0)
{
//set the value
parent = current;
current = current.right;
}
//otherwise
else
//return statement
return false;
//check the condition
if (e.compareTo (parent.element) < 0)
//create a new node
parent.left = createNewNode(e);
else
//create a new node
parent.right = createNewNode(e);
}
//increment the size
size++;
//return statement
return true;
}
//definition of "createNewNode"
protected TreeNode<E> createNewNode(E e)
{
//return the statement
return new TreeNode<E>(e);
}
//definition of "inorder"
public void inorder()
{
//inorder traverse from the root
inorder(root);
}
//definition of inorder
protected void inorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
// inorder traversal from a subtree
inorder(root.left);
//display the element
System.out.print(root.element + " ");
// inorder traversal from a subtree
inorder(root.right);
}
// definition of "postoder"
public void postorder()
{
// postorder traversal from the root
postorder(root);
}
// definition of "postorder"
protected void postorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
//postorder traversal from a subtree
postorder(root.left);
postorder(root.right);
//display the element
System.out.print(root.element + " ");
}
//definition of "preorder"
public void preorder()
{
// preorder traversal from the root
preorder(root);
}
//definition of "preorder"
protected void preorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
//display the value
System.out.print(root.element + " ");
// preorder traversal from a subtree
preorder(root.left);
preorder(root.right);
}
//definition of "TreeNode" class
public class TreeNode<E extends Comparable<E>>
{
//declare the variables
E element;
TreeNode<E> left;
TreeNode<E> right;
//definition of constructor
public TreeNode(E e)
{
//set the value
element = e;
}
}
// definition of "getSize" method
public int getSize()
{
//return statement
return size;
}
// definition of "getRoot" method
public TreeNode getRoot()
{
//return statement
return root;
}
// definition of method
public java.util.ArrayList<TreeNode<E>> path(E e)
{
//create an object
java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
// start from the root
TreeNode<E> current = root;
//check the condition
while (current != null)
{
//add the node to the list
list.add(current);
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
current = current.left;
}
//check the condition
else if (e.compareTo(current.element) > 0)
{
//set the value
current = current.right;
}
else
//break statement
break;
}
//return statement
return list;
}
//definition of "delete" method
public boolean delete(E e)
{
// declare the variables
TreeNode<E> parent = null;
TreeNode<E> current = root;
//check the condition
while (current != null)
{
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
parent = current;
current = current.left;
}
//check the condition
else if (e.compareTo(current.element) > 0)
{
//set the value
parent = current;
current = current.right;
}
else
//break statement
break;
}
//check the condition
if (current == null)
return false;
//check the condition
if (current.left == null)
{
//check the condition
if (parent == null)
{
//set the value
root = current.right;
}
else
{
//check the condition
if (e.compareTo(parent.element) < 0)
//set the value
parent.left = current.right;
else
//set the value
parent.right = current.right;
}
}
else
{
//set the value
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
//check the condition
while (rightMost.right != null)
{
//set the value
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
//set the value
current.element = rightMost.element;
//check the condition
if (parentOfRightMost.right == rightMost)
//set the value
parentOfRightMost.right = rightMost.left;
else
//set the value
parentOfRightMost.left = rightMost.left;
}
//decrement the "size"
size--;
//return statement
return true;
}
//definition of "iterator"
public java.util.Iterator<E> iterator()
{
//return statement
return inorderIterator();
}
//definition of "inorderIterator"
public java.util.Iterator<E> inorderIterator()
{
//return statement
return new InorderIterator();
}
// definition of class "InorderIterator"
class InorderIterator implements java.util.Iterator
{
// store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
//declare the variable
private int current = 0;
//constructor
public InorderIterator()
{
//call the method
inorder();
}
/*definition of inorder traversal from the root */
private void inorder()
{
//call the method
inorder(root);
}
/*definition of inorder traversal from a subtree */
private void inorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
//call the method
inorder(root.left);
//add the value to the list
list.add(root.element);
//call the method
inorder(root.right);
}
//definition of "hasNext"
public boolean hasNext()
{
//check the condition
if (current < list.size())
//return statement
return true;
//return statement
return false;
}
//definition of "next" method
public Object next()
{
//return statement
return list.get(current++);
}
// definition of "remove" method
public void remove()
{
//delete the current element
delete(list.get(current));
// clear the list
list.clear();
// rebuild the list
inorder();
}
}
// definition of "clear" method
public void clear()
{
//set the values
root = null;
size = 0;
}
}
//definition of interface
public interface Tree<E> extends java.util.Collection<E>
{
//declaration of methods
public boolean search(E e);
public boolean insert(E e);
public boolean delete(E e);
public int getSize();
// definition of default method
public default void inorder()
{
}
// definition of default method
public default void postorder()
{
}
// definition of default method
public default void preorder()
{
}
// definition of default method
public default boolean isEmpty()
{
//return statement
return size() == 0;
};
@Override
// definition of default method
public default boolean contains(Object e)
{
//return statement
return search((E)e);
}
@Override
// definition of default method
public default boolean add(E e)
{
//return statement
return insert(e);
}
@Override
// definition of default method
public default boolean remove(Object e)
{
//return statement
return delete((E)e);
}
@Override
// definition of default method
public default int size()
{
//return statement
return getSize();
}
@Override
// definition of default method
public default boolean containsAll(Collection<?> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default boolean addAll(Collection<? extends E> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default boolean removeAll(Collection<?> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default boolean retainAll(Collection<?> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default Object[] toArray()
{
//return statement
return null;
}
@Override
// definition of default method
public default <T> T[] toArray(T[] array)
{
//return statement
return null;
}
}
}
The height of tree is -1
Enter strings: aaa
bbb
ccc
ddd
eee
fff
The height of tree is 5
The height of tree is 5
aaa Green bbb ccc ddd eee fff
The breadth-first traversal is Tom George Jean Jane Kevin Jen Peter Kim Susan Michael Michelle
The height of tree1 is 7
The breadth-first traversal for tree2 is 50 45 59 35 48 51 58
The height of tree2 is 3
Want to see more full solutions like this?
Chapter 25 Solutions
Introduction to Java Programming and Data Structures, Comprehensive Version, Student Value Edition (11th Edition)
- Compute a Monte Carlo estimate o of 0.5 0 = L ē -xdx 0 by sampling from Uniform(0, 0.5). Find another Monte Carlo estimator 0* by sampling from the exponential distribution. Use simulations to estimate the variance of Ô and ⑦*, which estimator has smaller variance?arrow_forwardimport tkint class ShowInfoGUI:def __init__(self):# Create the main windowself.main_window = tkinter.Tk() # Create two framesself.top_frame = tkinter.Frame(self.main_window)self.bottom_frame = tkinter.Frame(self.main_window)arrow_forwardJOB UPDATE Apply on- COMPANY VinkJobs.com @ OR Search "Vinkjobs.com" on Google JOB PROFILE JOB LOCATION INTELLIFLO APPLICATION DEVELOPER MULTIPLE CITIES GLOBAL LOGIC SOFTWARE ENGINEER/SDET DELHI NCR SWIGGY SOFTWARE DEVELOPMENT BENGALURU AVALARA SOFTWARE ENGINEER (WFH) MULTIPLE CITIES LENSKART FULL STACK DEVELOPER MULTIPLE CITIES ACCENTURE MEDPACE IT CUST SERVICE SOFTWARE ENGINEER MUMBAI MUMBAI GENPACT BUSINESS ANALYST DELHI NCR WELOCALIZE WORK FROM HOME MULTIPLE CITIES NTT DATA BPO ASSOCIATE DELHI NCRarrow_forward
- How can predictive and prescriptive modeling be used to measure operational performance in real-time? Do you see any potential downsides to this application? Can you provide an example?arrow_forwardTracing the Recursion. Tracing the Recursion. Observe the recursive solution provided below. 1. Which line(s) of this program define(s) the base case of sumOfDigits() method? 2. Which line(s) of this program include recursive call(s)? 3. Trace the recursion below. You must show the trace step by step; otherwise – little to no credit! 4. Show me the final result! 1 public class SumOfDigitsCalculator { 30 123456 7% 8 public static void main(String[] args) { System.out.println(sumOfDigits(1234)); } public static int sumOfDigits (int number) { if (number == 0) 9 10 11 12 } 13 } else return 0; return number % 10 + sumOfDigits (number / 10);arrow_forwardmodule : java 731 Question3: (30 MARKS) Passenger Rail Agency for South Africa Train Scheduling System Problem Statement Design and implement a train scheduling system for Prasa railway network. The system should handle the following functionalities: 1. Scheduling trains: Allow the addition of train schedules, ensuring that no two trains use the same platform at the same time at any station. 2. Dynamic updates: Enable adding new train schedules and canceling existing ones. 3. Real-time simulation: Use multithreading to simulate the operation of trains (e.g., arriving, departing). 4. Data management: Use ArrayList to manage train schedules and platform assignments. Requirements 1. Add Train Schedule, Cancel Scheduled Train, View Train Schedules and Platform Management 2. Concurrency Handling with Multithreading i.e Use threads to simulate train operations,…arrow_forward
- please answer my 2 java questions correctly , include all comments etc and layout and structure must be correct , follow the requirementsarrow_forwardQuestion3: Passenger Rail Agency for South Africa Train Scheduling System Problem Statement (30 MARKS) Design and implement a train scheduling system for Prasa railway network. The system should handle the following functionalities: 1. Scheduling trains: Allow the addition of train schedules, ensuring that no two trains use the same platform at the same time at any station. 2. Dynamic updates: Enable adding new train schedules and canceling existing ones. 3. Real-time simulation: Use multithreading to simulate the operation of trains (e.g., arriving, departing). 4. Data management: Use ArrayList to manage train schedules and platform assignments. Requirements 1. Add Train Schedule, Cancel Scheduled Train, View Train Schedules and Platform Management 2. Concurrency Handling with Multithreading i.e Use threads to simulate train operations, Each train runs as a separate thread, simulating its arrival, departure, and travel status. 3. Use ArrayList to manage train schedules for each…arrow_forwardplease answer my java question correctly , include all comments etc and layout and structure must be correct , follow the requirementsarrow_forward
- C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage LearningSystems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage LearningNew Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage Learning
- EBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENTProgramming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage



