algoadvance

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

A height-balanced binary tree is defined as:

Clarifying Questions

  1. What is the input format?
    • The input is the root node of a binary tree.
  2. What is the output format?
    • The output should be a boolean value: True if the tree is height-balanced, otherwise False.
  3. Are there any constraints on the tree?
    • The number of nodes in the tree can range from 0 to (10^4).
  4. What should be returned for an empty tree?
    • An empty tree is considered height-balanced, so the function should return True.

Strategy

To determine if a binary tree is height-balanced, we can use a recursive approach. The idea is to check the heights of the left and right subtrees of every node and ensure the difference is no more than 1.

  1. Recursive Function: Implement a helper function that returns two values:
    • Whether the subtree is balanced.
    • The height of the subtree.

  2. Base Case: If a node is None (i.e., we have reached a leaf node’s child), it is considered balanced with a height of 0.

  3. Recursive Case:
    • Recur for the left and right subtrees.
    • If either subtree is unbalanced, propagate the unbalanced status upwards.
    • Otherwise, check the height difference of the left and right subtree.
    • If the height difference is more than 1, mark the current subtree as unbalanced.
    • Return the height as the maximum height of the two subtrees plus 1.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check_balance_and_height(node):
            # Base case: an empty subtree is balanced and has height 0
            if not node:
                return True, 0

            # Check left subtree
            left_balanced, left_height = check_balance_and_height(node.left)
            if not left_balanced:
                return False, 0

            # Check right subtree
            right_balanced, right_height = check_balance_and_height(node.right)
            if not right_balanced:
                return False, 0

            # Current node's balance check
            balanced = abs(left_height - right_height) <= 1
            height = max(left_height, right_height) + 1

            return balanced, height

        is_balanced, _ = check_balance_and_height(root)
        return is_balanced

Time Complexity

The time complexity of this solution is (O(N)), where (N) is the number of nodes in the tree. This is because each node in the tree is visited once.

Space Complexity

The space complexity is (O(H)) where (H) is the height of the tree. This is due to the recursion stack. In the worst case, the height of the tree could be (O(N)) (for a completely unbalanced tree), but on average for a balanced tree, it would be (O(\log N)).

Try our interview co-pilot at AlgoAdvance.com