Date: 2026-06-06
Time: 15:20
balanced-binary-tree/solution.pyThis file solves LeetCode #110 — Balanced Binary Tree. It determines whether a binary tree is height-balanced, meaning the left and right subtree depths of every node differ by at most 1. The file is self-contained: it defines the tree data structure, the solution logic, and a full test suite.
TreeNode — Standard binary tree node with val, left, right. Uses the union syntax (TreeNode | None) in the constructor signature alongside Optional[TreeNode] in the function signatures — a minor inconsistency but functionally identical.
getHeight(root) -> int — The core algorithm. This is a dual-purpose function: it computes the height of a subtree *and* detects imbalance, using -1 as a sentinel value meaning "this subtree is unbalanced." The contract is:
0 for None (base case — empty tree has height 0)-1 if any subtree is unbalancedmax(left, right) + 1 otherwise (standard height computation)isBalanced(root) -> bool — Thin wrapper that converts getHeight's integer signal into a boolean. The entire balance check is delegated to getHeight; this function exists solely to match the LeetCode API.
Sentinel return for early termination. Rather than computing heights in one pass and checking balance in another (O(n) space via a separate structure or O(n^2) time via redundant traversal), getHeight fuses both concerns into a single post-order traversal by using -1 as a "poison" value. Once any subtree returns -1, it propagates upward immediately — no further recursion into sibling subtrees occurs. This is the standard O(n) time, O(h) space solution for this problem.
Short-circuit evaluation. Lines 22–25 check left == -1 and right == -1 *before* recursing further or computing the balance condition. This means an unbalanced left subtree prevents any traversal of the right subtree, giving best-case performance better than a naive height-then-check approach.
Post-order traversal. The function processes children before the current node — left subtree height, then right subtree height, then the balance check at the current level. This is necessary because balance at a node depends on the heights of its children.
Imports: typing.Optional (for type annotations) and unittest (for inline tests). No external libraries.
Imported by: The "Imported By" list in the prompt is misleading — those are test files from *other* LeetCode problems that happen to share a common test runner or import pattern. The actual direct dependent is balanced-binary-tree/test_solution.py. The TreeNode class defined here is local to this file; other tree problems define their own TreeNode.
1. isBalanced(root) is called with the root of a binary tree.
2. It delegates to getHeight(root).
3. getHeight recurses post-order: left child → right child → current node.
4. At each node, if either child returned -1, return -1 immediately (propagate imbalance).
5. If abs(left - right) > 1, this node is the first point of imbalance — return -1.
6. Otherwise return max(left, right) + 1 (valid height).
7. isBalanced checks whether the result is -1 (unbalanced) or not.
getHeight returns a value in {-1} ∪ {0, 1, 2, ...}. It never returns any other negative number.getHeight returns a non-negative value h, then the subtree rooted at that node is balanced and has height exactly h.getHeight returns -1, at least one node in the subtree violates the balance property.None node is always balanced (height 0).None. The function assumes valid input (a proper binary tree or None). There's no cycle detection, no null-safety beyond the None base case, and no exception handling. This is appropriate for a LeetCode solution where inputs are guaranteed well-formed.