
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)
- Can I get help with this case please, thank youarrow_forwardI need help to solve the following, thank youarrow_forwardreminder it an exercice not a grading work GETTING STARTED Open the file SC_EX19_EOM2-1_FirstLastNamexlsx, available for download from the SAM website. Save the file as SC_EX19_EOM2-1_FirstLastNamexlsx by changing the “1” to a “2”. If you do not see the .xlsx file extension in the Save As dialog box, do not type it. The program will add the file extension for you automatically. With the file SC_EX19_EOM2-1_FirstLastNamexlsx still open, ensure that your first and last name is displayed in cell B6 of the Documentation sheet. If cell B6 does not display your name, delete the file and download a new copy from the SAM website. Brad Kauffman is the senior director of projects for Rivera Engineering in Miami, Florida. The company performs engineering projects for public utilities and energy companies. Brad has started to create an Excel workbook to track estimated and actual hours and billing amounts for each project. He asks you to format the workbook to make the…arrow_forward
- Need help with coding in this in python!arrow_forwardIn the diagram, there is a green arrow pointing from Input C (complete data) to Transformer Encoder S_B, which I don’t understand. The teacher model is trained on full data, but S_B should instead receive missing data—this arrow should not point there. Please verify and recreate the diagram to fix this issue. Additionally, the newly created diagram should meet the same clarity standards as the second diagram (Proposed MSCATN). Finally provide the output image of the diagram in image format .arrow_forwardPlease provide me with the output image of both of them . below are the diagrams code make sure to update the code and mentionned clearly each section also the digram should be clearly describe like in the attached image. please do not provide the same answer like in other question . I repost this question because it does not satisfy the requirment I need in terms of clarifty the output of both code are not very well details I have two diagram : first diagram code graph LR subgraph Teacher Model (Pretrained) Input_Teacher[Input C (Complete Data)] --> Teacher_Encoder[Transformer Encoder T] Teacher_Encoder --> Teacher_Prediction[Teacher Prediction y_T] Teacher_Encoder --> Teacher_Features[Internal Features F_T] end subgraph Student_A_Model[Student Model A (Handles Missing Values)] Input_Student_A[Input M (Data with Missing Values)] --> Student_A_Encoder[Transformer Encoder E_A] Student_A_Encoder --> Student_A_Prediction[Student A Prediction y_A] Student_A_Encoder…arrow_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



