Question

On page 372 of book, an unbalanced tree is defined as a tree that is created when most of the nodes are on one side of the root or the other. By this definition we will consider a tree balanced if total number of nodes in the left subtree of the root is equal to total number of nodes in the right subtree of the root.

Implement isBalancedByNodeCount() method with code below (With Java)

public class BinarySearchTree {
private Node root;

private boolean isBalancedByNodeCount() {
/****************************************************************************
Implement this method and replace the return statement below with your code.
* Definition of Balance tree (On page 372 of book):
* An unbalanced tree is created when most of the nodes are on one side of the root or the other.
****************************************************************************/
  
return false;
}
  
  
public static void main(String args[]) {
int[] values1 = {50, 25, 12, 23, 75, 65, 85};
int[] values2 = {50, 25, 12, 53, 75, 65, 85};
  
BinarySearchTree tree1 = new BinarySearchTree();
tree1.buildTreeFromArray(values1);
if (tree1.isBalancedByNodeCount())
System.out.println("Tree No. 1 is Balanced.");
else
System.out.println("Tree No. 1 is NOT Balanced!");
  
BinarySearchTree tree2 = new BinarySearchTree();
tree2.buildTreeFromArray(values2);
if (tree2.isBalancedByNodeCount())
System.out.println("Tree No. 2 is Balanced.");
else
System.out.println("Tree No. 2 is NOT Balanced!");
}
  
private void buildTreeFromArray(int[] values) {
for (int i = 0; i < values.length; i++) {
double d = values[i] * 2.5;
insert(values[i], d);
}
}
/***********************************************************************************
************ Code below this is copied from our implementation in class ************
************************************************************************************/
private void insert(int key, double data) {
Node n = new Node(key, data);
  
if (root == null)
root = n;
else {
Node current = root;
Node parent;
  
while (true) {
parent = current;
if (key < current.key) {
current = current.leftChild;
if (current == null) {
parent.leftChild = n;
return;
}
} else {
current = current.rightChild;
if (current == null) {
parent.rightChild = n;
return;
}
}
}   
}
}
}

class Node {
int key;
double data;
Node leftChild;
Node rightChild;
  
Node(int key, double data) {
this.key = key;
this.data = data;
}
  
void displayNode() {
System.out.println("{" + key + ", " + data +"}");
}
}

Answer 1

Answer:---                                                            Date:--26/10/2020

public class BinarySearchTree {

private Node root;

private boolean isBalancedByNodeCount() {

/**************************

Implement this method and replace the return statement below with your code.

* Definition of Balance tree (On page 372 of book):

* An unbalanced tree is created when most of the nodes are on one side of the root or the other.

**************************/

   class A{

       int numberOfNodes(Node node){

           if(node==null) return 0;

           return 1+numberOfNodes(node.leftChild)+numberOfNodes(node.rightChild);

       }

   }

   A ob = new A();

   if(ob.numberOfNodes(root.leftChild)==ob.numberOfNodes(root.rightChild))

       return true;

   return false;

}

public static void main(String args[]) {

int[] values1 = {50, 25, 12, 23, 75, 65, 85};

int[] values2 = {50, 25, 12, 53, 75, 65, 85};

BinarySearchTree tree1 = new BinarySearchTree();

tree1.buildTreeFromArray(values1);

if (tree1.isBalancedByNodeCount())

System.out.println("Tree No. 1 is Balanced.");

else

System.out.println("Tree No. 1 is NOT Balanced!");

BinarySearchTree tree2 = new BinarySearchTree();

tree2.buildTreeFromArray(values2);

if (tree2.isBalancedByNodeCount())

System.out.println("Tree No. 2 is Balanced.");

else

System.out.println("Tree No. 2 is NOT Balanced!");

}

private void buildTreeFromArray(int[] values) {

for (int i = 0; i < values.length; i++) {

double d = values[i] * 2.5;

insert(values[i], d);

}

}

/*****************************

**** Code below this is copied from our implementation in class ****

****************************/

private void insert(int key, double data) {

Node n = new Node(key, data);

if (root == null)

root = n;

else {

Node current = root;

Node parent;

while (true) {

parent = current;

if (key < current.key) {

current = current.leftChild;

if (current == null) {

parent.leftChild = n;

return;

}

} else {

current = current.rightChild;

if (current == null) {

parent.rightChild = n;

return;

}

}

}  

}

}

}

class Node {

int key;

double data;

Node leftChild;

Node rightChild;

Node(int key, double data) {

this.key = key;

this.data = data;

}

void displayNode() {

System.out.println("{" + key + ", " + data +"}");

}

}

Output:

Tree No. 1 is Balanced.

Tree No. 2 is NOT Balanced!

Note:

In the main method a logical error is found, instead of tree2.buildTreeFromArray(values1); it should be tree2.buildTreeFromArray(values2);

And another spelling mistake is found instead of int[] valeus2 = {50, 25, 12, 53, 75, 65, 85}; it should be

int[] values2 = {50, 25, 12, 53, 75, 65, 85};

plzzz rate me my answer....