Similar to a sorted array-based list, one of the main advantages of a binary search is that it is much quicker than a serial search because the data that needs to be searched halves with each step. For example, it is possible to search through 512 values and find the one you want within 9 steps, 1024 values in 10 steps, 2048 in 11 steps, and so on. However, not all tree ADT provides such benefits unless it is balanced. A balanced tree is defined as a tree where the depth of all leaf nodes or nodes with single children differs by no more than one. In other words, the height of a balanced tree is minimized. For this assignment, you will learn how to balance a tree.

In this assignment, we will implement several methods to facilitate tree ADT operations, including balancing a tree. Please implement those methods as required in the following steps.

/**

* Node.java: Node class
*/
public class Node{
private int data;
private Node left;
private Node right;
public Node(int data){
this.data =data;
left=right=null;
}
public int getData(){
return data;
}
public Node getLeft(){
return left;
}
public Node getRight(){
return right;
}
public void setLeft(Node node){
this.left = node;
}
public void setRight(Node node){
this.right = node;
}
public String toString(){
return ""+data;
}
}

Page

of 3

ZOOM

/**

*
* MyIntBSTTree.txt: the template file of MyIntBSTTree.java
* Student tasks: implement tasks #1-#3 as specified in this file
*/
import java.util.*;
public class MyIntBSTTree{
private Node root;
public MyIntBSTTree(){
root=null;
}
public int height(){
// *** Student task #1 ***
/* Requirements:
The height of a binary tree is the largest number of edges in a
path from the root node to a leaf node.
Essentially, it is the height of the root node. Note that if a
tree has only one node, then that node
is at the same time the root node and the only leaf node, so the
height of the tree is 0, similary,
the height of a tree with only two nodes is 1.
- Implement this method to return height of the tree
*** Enter your code below ***
*/
}
public Node[] inOrderArray(){
// *** Student task #2 ***
/* Requirements:
This method get all elements in the tree and return them as
sorted Node array
*** Enter your code below ***
*/

}
public MyIntBSTTree balance(){
// *** Student task #3 ***
/* Requirements:
This method rebuilds three to minimize the level (height) of the
tree.
To do so, you are going to rebuild a new tree from the ordered
node elelemts array.
To minimize the height of the tree, for any node, you try to keep
balanced numbers
of it's left and right subtrees. Please following the steps to
achieve this goal:
1. select and add the middle element of the array,the middle
element divides the
arry into two parts: part1-(before middle one) and part2-
(after the middle one)
2. For part1 and part2, go to step 1. Repet the process until
all elements are added.
For example, for an array {1,3,6,8,9,12,20}, add 8 to tree,
the middle value 8 divides
the array into two parts: Part 1: {1,3,6} and Part 2:
{9,12,20}, for part 1, add 3,
for part 2, add 12, repeat the process until all elements are
added.
3. Return the newly builded tree.
*** Enter your code below ***
*/
}
public void add(int data) {
root = addHelper(root, data);
}
private Node addHelper(Node node, int data) {//add node helper
if (node == null){
node = new Node(data);
}else if (data <= node.getData()){
node.setLeft(addHelper(node.getLeft(), data));
}else{
node.setRight(addHelper(node.getRight(),
data));//System.out.println(data);
}
return node;
}
public void display(){

//print tree structure
displayHelper(root, 0);
}
private void displayHelper(Node t, int level){
if(t==null) return ;
displayHelper(t.getRight(), level + 1);
for(int k = 0; k < level; k++)
System.out.print("\t");
System.out.println(t.getData());
displayHelper(t.getLeft(), level + 1); //recurse left
}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(Node node){
if(node==null) return 0;
else return
1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
}//print tree structure
displayHelper(root, 0);
}
private void displayHelper(Node t, int level){
if(t==null) return ;
displayHelper(t.getRight(), level + 1);
for(int k = 0; k < level; k++)
System.out.print("\t");
System.out.println(t.getData());
displayHelper(t.getLeft(), level + 1); //recurse left
}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(Node node){
if(node==null) return 0;
else return
1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
}

ZOOM

/**

*
* GA2Driver.java: the driver program for MyIntBSTTree class
*/
public class GA2Driver{
public static void main(String[] args){

MyIntBSTTree tree=new MyIntBSTTree();

tree.add(1);
tree.add(3);
tree.add(4);
tree.add(12);
tree.add(20);
tree.add(26);
tree.add(68);

System.out.println("Before balancing:");
System.out.println("Tree height: "+ tree.height());
tree.display();

System.out.println("\n\nAfter balancing:");
tree = tree.balance();
System.out.println("Tree height: "+ tree.height());
tree.display();
}
}

Question

Similar to a sorted array-based list, one of the main advantages of a binary search is that it is much quicker than a serial search because the data that needs to be searched halves with each step. For example, it is possible to search through 512 values and find the one you want within 9 steps, 1024 values in 10 steps, 2048 in 11 steps, and so on. However, not all tree ADT provides such benefits unless it is balanced. A balanced tree is defined as a tree where the depth of all leaf nodes or nodes with single children differs by no more than one. In other words, the height of a balanced tree is minimized. For this assignment, you will learn how to balance a tree.

In this assignment, we will implement several methods to facilitate tree ADT operations, including balancing a tree. Please implement those methods as required in the following steps.

/**

* Node.java: Node class
*/
public class Node{
private int data;
private Node left;
private Node right;
public Node(int data){
this.data =data;
left=right=null;
}
public int getData(){
return data;
}
public Node getLeft(){
return left;
}
public Node getRight(){
return right;
}
public void setLeft(Node node){
this.left = node;
}
public void setRight(Node node){
this.right = node;
}
public String toString(){
return ""+data;
}
}

Page

of 3

ZOOM

/**

*
* MyIntBSTTree.txt: the template file of MyIntBSTTree.java
* Student tasks: implement tasks #1-#3 as specified in this file
*/
import java.util.*;
public class MyIntBSTTree{
private Node root;
public MyIntBSTTree(){
root=null;
}
public int height(){
// *** Student task #1 ***
/* Requirements:
The height of a binary tree is the largest number of edges in a
path from the root node to a leaf node.
Essentially, it is the height of the root node. Note that if a
tree has only one node, then that node
is at the same time the root node and the only leaf node, so the
height of the tree is 0, similary,
the height of a tree with only two nodes is 1.
- Implement this method to return height of the tree
*** Enter your code below ***
*/
}
public Node[] inOrderArray(){
// *** Student task #2 ***
/* Requirements:
This method get all elements in the tree and return them as
sorted Node array
*** Enter your code below ***
*/

}
public MyIntBSTTree balance(){
// *** Student task #3 ***
/* Requirements:
This method rebuilds three to minimize the level (height) of the
tree.
To do so, you are going to rebuild a new tree from the ordered
node elelemts array.
To minimize the height of the tree, for any node, you try to keep
balanced numbers
of it's left and right subtrees. Please following the steps to
achieve this goal:
1. select and add the middle element of the array,the middle
element divides the
arry into two parts: part1-(before middle one) and part2-
(after the middle one)
2. For part1 and part2, go to step 1. Repet the process until
all elements are added.
For example, for an array {1,3,6,8,9,12,20}, add 8 to tree,
the middle value 8 divides
the array into two parts: Part 1: {1,3,6} and Part 2:
{9,12,20}, for part 1, add 3,
for part 2, add 12, repeat the process until all elements are
added.
3. Return the newly builded tree.
*** Enter your code below ***
*/
}
public void add(int data) {
root = addHelper(root, data);
}
private Node addHelper(Node node, int data) {//add node helper
if (node == null){
node = new Node(data);
}else if (data <= node.getData()){
node.setLeft(addHelper(node.getLeft(), data));
}else{
node.setRight(addHelper(node.getRight(),
data));//System.out.println(data);
}
return node;
}
public void display(){

//print tree structure
displayHelper(root, 0);
}
private void displayHelper(Node t, int level){
if(t==null) return ;
displayHelper(t.getRight(), level + 1);
for(int k = 0; k < level; k++)
System.out.print("\t");
System.out.println(t.getData());
displayHelper(t.getLeft(), level + 1); //recurse left
}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(Node node){
if(node==null) return 0;
else return
1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
}//print tree structure
displayHelper(root, 0);
}
private void displayHelper(Node t, int level){
if(t==null) return ;
displayHelper(t.getRight(), level + 1);
for(int k = 0; k < level; k++)
System.out.print("\t");
System.out.println(t.getData());
displayHelper(t.getLeft(), level + 1); //recurse left
}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(Node node){
if(node==null) return 0;
else return
1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
}

ZOOM

/**

*
* GA2Driver.java: the driver program for MyIntBSTTree class
*/
public class GA2Driver{
public static void main(String[] args){

MyIntBSTTree tree=new MyIntBSTTree();

tree.add(1);
tree.add(3);
tree.add(4);
tree.add(12);
tree.add(20);
tree.add(26);
tree.add(68);

System.out.println("Before balancing:");
System.out.println("Tree height: "+ tree.height());
tree.display();

System.out.println("\n\nAfter balancing:");
tree = tree.balance();
System.out.println("Tree height: "+ tree.height());
tree.display();
}
}

After balancing:&#34;);tree = tree.balance();System.out.println(&#34;Tree height: &#34;+ tree.height());tree.display();}}

Accepted Answer

Coded using Java.