Java Program to check the Binary tree is balanced or not

    A binary tree has exactly two nodes for each parent node. Sometimes, sub parent has less than two nodes or no nodes at all. For this type of binary trees, we check the tree balance.

Logic:

• ·       A tree is created with left and right child with data.
• ·       Right side height is calculated.
• ·       Left side height is calculated.
• ·       Check the balance.
• ·       If both are equal, then the binary tree is balanced. Otherwise, it is not balanced.

 Let us implement this in java.

Program implementation:

• A tree structure is created with integer data, left and right child.
• A constructor is used to initialise the value.
• A public class is created with three member function.
• ‘balanceIt()’ – it checks the balance of tree.
• ‘checkHeight()’ -it finds the height of given tree.
• ‘main()’ – As usual, this function creates the object for the public class.
• It reads the tree values.
• Calls the ‘balanceIt()’ function to get the balanced tree value.

Program:

class Tree_Node {

    int data;

    Tree_Node left;

    Tree_Node right;

 

    Tree_Node(int x) {

        data = x;

    }

}

 

public class BalancedBinaryTreeEg {

 

    public boolean balancedIt(Tree_Node root) {

        return checkHeight(root) != -1;

    }

 

    private int checkHeight(Tree_Node node) {

        if (node == null) {

            return 0;

        }

 

        int leftHeight = checkHeight(node.left);

        if (leftHeight == -1) return -1;

 

        int rightHeight = checkHeight(node.right);

        if (rightHeight == -1) return -1;

 

        if (Math.abs(leftHeight - rightHeight) > 1) {

            return -1; // it means tree is not balanced

        }

 

        return Math.max(leftHeight, rightHeight) + 1;

    }

 

    public static void main(String[] args) {

        BalancedBinaryTreeEg t1 = new BalancedBinaryTreeEg();

        boolean check;

        Tree_Node root = new Tree_Node(1);

        root.left = new Tree_Node(2);

        root.right = new Tree_Node(3);

        root.left.left = new Tree_Node(4);

        root.left.right = new Tree_Node(5);

        root.left.left.left = new Tree_Node(8);

        check = t1.balancedIt(root);

        if(check)

        {

         System.out.println("The binary tree is balanced");

          }

        else

        {

         System.out.println("The Binary tree is not balanced");

        }

    }

}

Output:

Just compile and execute the program to get the output.

C:\raji\blog>javac BalancedBinaryTreeEg.java

C:\raji\blog>java BalancedBinaryTreeEg

The Binary tree is not balanced

This is the way to check the given binary tree is balanced or not in java. Hope, this code is useful to you. Keep coding!!!