Balanced Binary Tree - Java Solution

1. Introduction

This blog post addresses the Balanced Binary Tree problem, a fundamental concept in binary trees. We will explore how to determine if a binary tree is height-balanced using Java. A height-balanced tree is crucial for maintaining efficient operations like insertion and search.

Problem

Given a binary tree, the task is to determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Example 1:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

2. Solution Steps

1. Create a method to calculate the height of a binary tree from a given node.

2. In the height method, check if the tree is unbalanced. If unbalanced, return an error code (-1).

3. Check if the absolute difference in height between the left and right subtrees is more than 1 at any node.

4. If the height difference is more than 1, or if any subtree is unbalanced, conclude that the tree is not height-balanced.

5. Otherwise, return true indicating the tree is height-balanced.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println("Is height-balanced: " + isBalanced(root));
    }

    // Method to check if the tree is height-balanced
    public static boolean isBalanced(TreeNode root) {
        return height(root) != -1; // A return value of -1 indicates unbalanced tree
    }

    // Helper method to compute the height and check balancing
    private static int height(TreeNode node) {
        if (node == null) return 0; // Base case: height of null is 0

        int leftHeight = height(node.left); // Height of left subtree
        if (leftHeight == -1) return -1; // Left subtree is unbalanced

        int rightHeight = height(node.right); // Height of right subtree
        if (rightHeight == -1) return -1; // Right subtree is unbalanced

        if (Math.abs(leftHeight - rightHeight) > 1) return -1; // Current node is unbalanced

        return Math.max(leftHeight, rightHeight) + 1; // Return height of the current node
    }
}

Output:

Is height-balanced: true

Explanation:

The given binary tree is balanced as the heights of the left and right subtrees of all nodes differ by no more than 1. 

The isBalanced method calls the height method for each node to calculate its height and check if the subtrees are balanced. The tree in the example has a balanced structure, therefore, the output is true.