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.
Comments
Post a Comment
Leave Comment