Answer:
See explaination
Explanation:
// Class for BinarySearchTreeNode
class TreeNode
{
// To store key value
public int key;
// To point to left child
public TreeNode left;
// To point to right child
public TreeNode right;
// Default constructor to initialize instance variables
public TreeNode(int key)
{
this.key = key;
left = null;
right = null;
key = 0;
}// End of default constructor
}// End of class
// Defines a class to crate binary tree
class BinaryTree
{
// Creates root node
TreeNode root;
int numberElement;
// Default constructor to initialize root
public BinaryTree()
{
this.root = null;
numberElement = 0;
}// End of default constructor
// Method to insert key
public void insert(int key)
{
// Creates a node using parameterized constructor
TreeNode newNode = new TreeNode(key);
numberElement++;
// Checks if root is null then this node is the first node
if(root == null)
{
// root is pointing to new node
root = newNode;
return;
}// End of if condition
// Otherwise at least one node available
// Declares current node points to root
TreeNode currentNode = root;
// Declares parent node assigns null
TreeNode parentNode = null;
// Loops till node inserted
while(true)
{
// Parent node points to current node
parentNode = currentNode;
// Checks if parameter key is less than the current node key
if(key < currentNode.key)
{
// Current node points to current node left
currentNode = currentNode.left;
// Checks if current node is null
if(currentNode == null)
{
// Parent node left points to new node
parentNode.left = newNode;
return;
}// End of inner if condition
}// End of outer if condition
// Otherwise parameter key is greater than the current node key
else
{
// Current node points to current node right
currentNode = currentNode.right;
// Checks if current node is null
if(currentNode == null)
{
// Parent node right points to new node
parentNode.right = newNode;
return;
}// End of inner if condition
}// End of outer if condition
}// End of while
}// End of method
// Method to check tree is balanced or not
private int checkBalance(TreeNode currentNode)
{
// Checks if current node is null then return 0 for balanced
if (currentNode == null)
return 0;
// Recursively calls the method with left child and
// stores the return value as height of left sub tree
int leftSubtreeHeight = checkBalance(currentNode.left);
// Checks if left sub tree height is -1 then return -1
// for not balanced
if (leftSubtreeHeight == -1)
return -1;
// Recursively calls the method with right child and
// stores the return value as height of right sub tree
int rightSubtreeHeight = checkBalance(currentNode.right);
// Checks if right sub tree height is -1 then return -1
// for not balanced
if (rightSubtreeHeight == -1) return -1;
// Checks if left and right sub tree difference is greater than 1
// then return -1 for not balanced
if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1)
return -1;
// Returns the maximum value of left and right subtree plus one
return (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1);
}// End of method
// Method to calls the check balance method
// returns false for not balanced if check balance method returns -1
// otherwise return true for balanced
public boolean balanceCheck()
{
// Calls the method to check balance
// Returns false for not balanced if method returns -1
if (checkBalance(root) == -1)
return false;
// Otherwise returns true
return true;
}//End of method
// Method for In Order traversal
public void inorder()
{
inorder(root);
}//End of method
// Method for In Order traversal recursively
private void inorder(TreeNode root)
{
// Checks if root is not null
if (root != null)
{
// Recursively calls the method with left child
inorder(root.left);
// Displays current node value
System.out.print(root.key + " ");
// Recursively calls the method with right child
inorder(root.right);
}// End of if condition
}// End of method
}// End of class BinaryTree
// Driver class definition
class BalancedBinaryTreeCheck
{
// main method definition
public static void main(String args[])
{
// Creates an object of class BinaryTree
BinaryTree treeOne = new BinaryTree();
// Calls the method to insert node
treeOne.insert(1);
treeOne.insert(2);
treeOne.insert(3);
treeOne.insert(4);
treeOne.insert(5);
treeOne.insert(8);
// Calls the method to display in order traversal
System.out.print("\n In order traversal of Tree One: ");
treeOne.inorder();
if (treeOne.balanceCheck())
System.out.println("\n Tree One is balanced");
else
System.out.println("\n Tree One is not balanced");
BinaryTree
BinaryTree treeTwo = new BinaryTree();
treeTwo.insert(10);
treeTwo.insert(18);
treeTwo.insert(8);
treeTwo.insert(14);
treeTwo.insert(25);
treeTwo.insert(9);
treeTwo.insert(5);
System.out.print("\n\n In order traversal of Tree Two: ");
treeTwo.inorder();
if (treeTwo.balanceCheck())
System.out.println("\n Tree Two is balanced");
else
System.out.println("\n Tree Two is not balanced");
}// End of main method
}// End of driver class
