How Can I Determine If a Binary Tree Is Height-Balanced?

How can I determine if a binary tree is height-balanced?

public boolean isBalanced(Node root) {
    if (root == null) {
        return true;  // tree is empty
    }
    int lh = height(root.left);
    int rh = height(root.right);
    return Math.abs(lh - rh) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

private int height(Node node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

Determining if a binary tree is height-balanced involves ensuring that the heights of the two child subtrees of any node differ by no more than one. A balanced tree provides optimal performance for operations such as insertion, deletion, and lookup. This process can be implemented efficiently using a recursive approach.

public boolean isBalanced(Node root) {
    if (root == null) {
        return true;  // tree is empty
    }
    int lh = height(root.left);
    int rh = height(root.right);
    if (Math.abs(lh - rh) > 1) {
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
}

private int height(Node node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

Causes

• Unbalanced branches due to uneven heights of child nodes.
• Improper insertion order affecting the tree structure.
• Manipulation of the tree without following balance rules.

Solutions

• Use a recursive function to calculate heights of subtrees while checking balance concurrently.
• Implement self-balancing trees like AVL or Red-Black trees to maintain balance after each operation.

Mistake: Not checking both left and right subtrees for balance.

Solution: Ensure to check balance for both child nodes recursively.

Mistake: Returning early if only one subtree is of unwanted height.

Solution: Both subtrees' heights must be checked prior to returning.