💬 Discord
Sign In
NeetCode #389LC-110EasyTreesNC 150NC 250
← Back to All Problems

#389 · #110 · Balanced Binary Tree(平衡二叉树)

📌 Problem Statement & Constraints

Given a binary tree, determine whether it is height-balanced: for every node, the heights of its two subtrees differ by at most 1. Constraints: the number of nodes is in [0, 5000].

💡 Core Algorithmic Approaches

  1. A naive check computes the height of every node's subtrees, which is O(n^2).
  2. Instead, do a single post-order traversal that returns the height, or -1 to signal an imbalance.
  3. As soon as a subtree reports -1, propagate it upward without further work.
  4. This gives O(n) with no repeated height computation.

💻 Benchmark Python3 Implementation

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node: Optional[TreeNode]) -> int:
            """Return the height, or -1 if the subtree is unbalanced."""
            if not node:
                return 0
            l = check(node.left)
            if l == -1:
                return -1                  # short-circuit
            r = check(node.right)
            if r == -1:
                return -1
            if abs(l - r) > 1:
                return -1                  # imbalance found here
            return 1 + max(l, r)

        return check(root) != -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Computing maxDepth separately for every node: O(n^2) because the heights are recomputed.
  • Forgetting the short-circuit: without returning early, a subtree's imbalance would be masked by a balanced ancestor.
  • Using >= 1 instead of > 1: a difference of exactly 1 is allowed.
  • Returning a boolean from the helper: the height must be propagated, so the sentinel -1 is the idiomatic encoding.