0110_balanced_binary_tree.py

"""110. Balanced Binary Tree  —  Easy

LeetCode: https://leetcode.com/problems/balanced-binary-tree/

Problem
-------
A height-balanced binary tree is defined as one where the heights of the left
and right subtrees of EVERY node differ by at most one.  Given the root of a
binary tree, return True if it is height-balanced, False otherwise.

Examples
--------
    Input:  root = [3, 9, 20, null, null, 15, 7]
    Output: True

    Input:  root = [1, 2, 2, 3, 3, null, null, 4, 4]
    Output: False

    Input:  root = []
    Output: True

Intuition
---------
Compute height bottom-up; if any subtree is already unbalanced, propagate a
sentinel value (-1) upward to short-circuit the whole traversal.

Approach
--------
1. Define a helper that returns the height of a subtree, or -1 if that subtree
   is already unbalanced.
2. At each node: get left_height and right_height (each may be -1).
3. If either child returned -1, or |left_height - right_height| > 1, return -1
   (unbalanced).
4. Otherwise return 1 + max(left_height, right_height).
5. The outer function returns True iff the helper returns a value >= 0.

Brute force would recompute heights from scratch at every node → O(n log n).
The sentinel approach avoids recomputation: O(n) with a single DFS pass.

The return value of each recursive call is a *dual-purpose* quantity: a
non-negative integer when balanced (the height), -1 as a poison pill when not.

Complexity
----------
Time:  O(n)   single post-order DFS.
Space: O(h)   call-stack depth.

Edge cases
----------
- Empty tree → True.
- Single node → True (height 1, both children have height 0).
- Deeply skewed tree → False.

Pattern: DFS Recursion (post-order) with sentinel / early exit.
ML relevance: Verifying that a constructed decision-tree ensemble is
              structurally balanced, which affects prediction latency.
"""
from __future__ import annotations

from collections import deque
from typing import Optional


class TreeNode:
    """Standard LeetCode binary-tree node."""

    def __init__(
        self,
        val: int = 0,
        left: Optional[TreeNode] = None,
        right: Optional[TreeNode] = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """LeetCode submission class."""

    def isBalanced(self, root: Optional[TreeNode]) -> bool:  # noqa: N802
        """Return True iff the tree is height-balanced."""
        return self._check_height(root) != -1

    def _check_height(self, node: Optional[TreeNode]) -> int:
        """Return the height of node's subtree, or -1 if unbalanced."""
        if node is None:
            return 0
        left_h = self._check_height(node.left)
        if left_h == -1:
            return -1  # short-circuit: left subtree already unbalanced
        right_h = self._check_height(node.right)
        if right_h == -1:
            return -1  # short-circuit: right subtree already unbalanced
        if abs(left_h - right_h) > 1:
            return -1  # this node violates the balance condition
        return 1 + max(left_h, right_h)


# ---------------------------------------------------------------------------
# Helpers
# ---------------------------------------------------------------------------

def _build_tree(values: list[int | None]) -> Optional[TreeNode]:
    """Build a binary tree from a LeetCode-style level-order list."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])  # type: ignore[arg-type]
    queue: deque[TreeNode] = deque([root])
    index = 1
    while queue and index < len(values):
        node = queue.popleft()
        if index < len(values) and values[index] is not None:
            node.left = TreeNode(values[index])  # type: ignore[arg-type]
            queue.append(node.left)
        index += 1
        if index < len(values) and values[index] is not None:
            node.right = TreeNode(values[index])  # type: ignore[arg-type]
            queue.append(node.right)
        index += 1
    return root


def _demo() -> None:
    """Run worked examples as assertions."""
    solver = Solution()

    # Balanced
    assert solver.isBalanced(_build_tree([3, 9, 20, None, None, 15, 7])) is True

    # Unbalanced
    assert solver.isBalanced(
        _build_tree([1, 2, 2, 3, 3, None, None, 4, 4])
    ) is False

    # Empty tree
    assert solver.isBalanced(None) is True

    # Single node
    assert solver.isBalanced(_build_tree([1])) is True

    # Skewed to the left → unbalanced
    assert solver.isBalanced(_build_tree([1, 2, None, 3, None, 4])) is False

    print("All tests passed.")


if __name__ == "__main__":
    _demo()