algoadvance

Leetcode 110. Balanced Binary Tree

Problem Statement

Leetcode Problem 110: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is defined as:

  1. A binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Clarifying Questions

  1. Input: What is the type of input for the tree (e.g., array, TreeNode)?
    • Answer: The input will be a TreeNode, which is the root of the binary tree.
  2. Edge Cases: How should specific edge cases be handled, such as an empty tree?
    • Answer: An empty tree (where the root is null) is considered balanced.

Strategy

To determine whether a binary tree is height-balanced:

  1. We need to calculate the height of the left and right subtree of every node.
  2. We then check the difference in heights. If the difference is greater than 1 for any node, the tree is not balanced.
  3. We can achieve this efficiently by using a recursive approach:
    • Compute the height of the left and right subtrees.
    • If at any point the subtrees differ in height by more than 1, we can immediately return false.
    • Otherwise, we return true if all nodes are balanced.

We will modify the height computation to also return a special value (e.g., -1) if it finds an unbalanced subtree. This helps us avoid redundant computations.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }
    
    private int checkHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) {
            return -1;
        }
        
        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) {
            return -1;
        }
        
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because in the worst case, we visit each node once and perform a constant amount of work at each node.

The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI