Determining if a Binary Tree is Balanced in Java

A binary tree is considered balanced if the depth of its two subtrees for any given node never differs by more than one. In this blog post, we'll dive into a Java program that checks if a binary tree is balanced. We'll walk you through the entire process, from understanding the core logic to implementing the code and interpreting the output. 

Understanding the Logic 

Before we dive into the code, let's first understand the logic. For every node: 

1. Calculate the height of the left and right subtrees. 
2. If the difference in heights is more than 1, or if any of the subtrees is unbalanced, the tree is not balanced. 

Program Implementation

// Define the node structure
class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int item) {
        value = item;
        left = right = null;
    }
}

public class BinaryTree {
    
    TreeNode root;  // Root of the binary tree

    // Utility function to determine the height of the tree
    public int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // Function to check if the tree is balanced
    public boolean isBalanced(TreeNode node) {
        if (node == null) {
            return true;  // Base case
        }
        
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        return (Math.abs(leftHeight - rightHeight) <= 1) && 
               isBalanced(node.left) && 
               isBalanced(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        
        // Create nodes of the tree
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        tree.root.left.left.left = new TreeNode(8);

        if (tree.isBalanced(tree.root)) {
            System.out.println("The tree is balanced");
        } else {
            System.out.println("The tree is not balanced");
        }
    }
}

Output:

The tree is not balanced

Step-by-step Explanation: 

TreeNode Class: 

• This defines the structure of a node in our binary tree. Each node contains a value and pointers to its left and right child nodes. 

height Method:

• It's a helper method that computes the height of the tree recursively. 
• If the node is null, the height is zero. Otherwise, the height is 1 (for the current node) plus the maximum of the heights of the left and right children. 

isBalanced Method: 

• This method is the core of our program. It checks if a binary tree is balanced. 
• For each node, it calculates the heights of the left and right subtrees. If the difference is more than 1, or if any of the subtrees is not balanced, it returns false. 
• If the tree passes these checks for all nodes, the method returns true, indicating the tree is balanced.

main Method: 

• We instantiate the BinaryTree class and create a sample binary tree. 
• We then call the isBalanced method on the root of the tree and print out the result. 

In the given sample tree, the left subtree has a height of 3 (from root to the deepest node 8), while the right subtree has a height of just 1. Since the difference is 2 (which is greater than 1), the program correctly determines that the tree is not balanced.