# The Balanced Inspector

> Every branch should carry the same weight.

Canonical URL: <https://datadriven.io/problems/the_balanced_inspector>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a binary tree represented as a dict with keys 'val', 'left', 'right' (subtrees or None), return True if for every node the heights of its left and right subtrees differ by at most 1 AND both subtrees are balanced.

## Worked solution and explanation

### Why this problem exists in real interviews

Checking if a binary tree is height-balanced tests **recursive tree traversal** with an optimization twist: you can compute height and check balance in a single pass by returning -1 for unbalanced subtrees.

---

### Break down the requirements

#### Step 1: Compute the height of each subtree recursively

A leaf node has height 0. Each parent's height is 1 + max(left height, right height).

#### Step 2: Check balance at each node

A node is balanced if the left and right subtree heights differ by at most 1.

#### Step 3: Propagate imbalance upward

If any subtree is unbalanced, return -1 to short-circuit further computation.

---

### The solution

**Single-pass recursive height check with early termination**

```python
def is_balanced(root):
    def check_height(node):
        if node is None:
            return 0
        left_height = check_height(node.left)
        if left_height == -1:
            return -1
        right_height = check_height(node.right)
        if right_height == -1:
            return -1
        if abs(left_height - right_height) > 1:
            return -1
        return 1 + max(left_height, right_height)
    return check_height(root) != -1
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of nodes. Each node is visited exactly once.
> 
> **Space:** O(h) where h is the tree height, for the recursion stack.

> **Interviewers Watch For**
>
> The -1 sentinel for early termination. A naive approach that computes height and checks balance separately would be O(n^2) since height is recomputed at every level.

> **Common Pitfall**
>
> Computing `height(node.left)` and `height(node.right)` in separate functions and then checking the difference. This works but is O(n log n) for balanced trees and O(n^2) for skewed trees.

---

## Common follow-up questions

- How would you balance an unbalanced BST? _(Tests converting to a sorted array and rebuilding with a balanced BST construction (divide and conquer).)_
- What is the difference between height-balanced and weight-balanced? _(Tests understanding that weight-balanced considers the number of nodes in each subtree, not just height.)_
- What is the maximum height of a balanced BST with n nodes? _(Tests knowledge that it is O(log n), specifically `floor(log2(n))` for a perfect tree.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_balanced_inspector)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.