Java Program to Check if a Binary Tree is Height-Balanced

This Java program determines whether a binary tree is height-balanced. A tree is considered balanced if for every node, the height difference between its left and right subtrees is no more than one. This property is crucial for ensuring that operations such as insertion, deletion, and lookup can be performed with optimal time complexity.

Binary Tree Class

The BinaryTree class defines the structure of the tree and includes a method to check if the tree is balanced. The method returns a height if the tree is balanced, and -1 if it is not, which simplifies the process of checking balance throughout the tree.

public class BinaryTree {
    static class Node {
        int value;
        Node left, right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    Node root;

    public BinaryTree() {
        root = null;
    }

    // Method to check if the binary tree is balanced
    public boolean isBalanced(Node node) {
        return checkHeight(node) != -1;
    }

    // Helper method to check the height and balance of the tree
    private int checkHeight(Node node) {
        if (node == null) {
            return 0; // Base case: the height of an empty subtree is 0
        }

        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) return -1; // Left subtree is not balanced

        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) return -1; // Right subtree is not balanced

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // Current node is not balanced
        } else {
            return Math.max(leftHeight, rightHeight) + 1; // Return height if balanced
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.left.left.left = new Node(6);

        System.out.println("Is the binary tree balanced? " + tree.isBalanced(tree.root));
    }
}

Explanation of the Methods

• isBalanced – This public method is used to initiate the balance checking process. It returns true if the tree is balanced and false otherwise.
• checkHeight – This private helper method recursively checks if each subtree is balanced while calculating their heights. It returns the height of the subtree if it is balanced, and -1 if it is not.

Conclusion

The provided Java implementation effectively checks if a binary tree is height-balanced by integrating height calculations with balance checking, thus optimizing performance by avoiding redundant calculations. This method is essential for maintaining efficient operations in balanced trees, such as AVL trees and Red-Black trees.