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 this code below:

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[] valeus2 = {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(values1);
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 +"}");
}
}

IN JAVA PLEASE

Answer 1

Program

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};

Solving your question and helping you to well understand it is my focus. So if you face any difficulties regarding this please let me know through the comments. I will try my best to assist you. However if you are satisfied with the answer please don't forget to give your feedback. Your feedback is very precious to us, so don't give negative feedback without showing proper reason.

Thank you.