The Balanced Inspector

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

You're validating binary trees coming out of a parser, each given as a nested dict with keys val, left, and right, where a missing child is None and the whole tree may itself be None. Return True when the tree is height-balanced: at every node the heights of the left and right subtrees differ by at most 1. An empty tree counts as balanced.

Every branch should carry the same weight.

Example 1

Input:

root = {"val":3,"left":{"val":9,"left":null,"right":null},"right":{"val":20,"left":{"val":15,"left":null,"right":null},"right":{"val":7,"left":null,"right":null}}}

Output:

true

Example 2

Input:

root = {"val":1,"left":{"val":2,"left":{"val":3,"left":{"val":4,"left":null,"right":null},"right":null},"right":null},"right":{"val":2,"left":null,"right":null}}

Output:

false

Worked solution and explanation

What this really is

This is a whole-tree invariant check dressed up as parser validation. The question is not whether the root looks even. It is whether every node does. The trap is computing the left and right heights once at the root and calling it done: a tree can show 4 and 3 at the root while a node two levels down has a branch of height 2 against an empty side. Get that wrong and you stamp 'balanced' on a degenerate tree that downstream code assumes is shallow. The second trap comes after you get per-node checking right: calling a standalone height() at every node re-walks the lower levels and goes O(n^2) on a skewed tree. A single post-order recursion avoids both traps. It returns a height, or -1 the instant any subtree fails, and that -1 rides straight up to the root.

Break down the requirements

Step 1: Compute each subtree's height on the way back up

Each node is a dict with keys 'val', 'left' and 'right', and a missing branch is None. A None subtree has height 0. Any other node's height is 1 plus the taller of its two children. Read children with node['left'] and node['right'], after you have ruled out None.

Step 2: Test the difference at every node

A node is balanced when its two subtree heights differ by at most 1. The check runs inside the recursion, so it fires at every node rather than once at the root. That is what catches an imbalance buried under an even-looking root.

Step 3: Propagate failure with a sentinel, from both sides

Once a subtree is unbalanced, return -1 instead of a height, and have every caller bail on -1 before doing anything else. Check it on the right as well as the left. If you skip the right-side check, a broken right subtree next to a missing left child compares -1 against 0, passes the difference test, and reports a height of 1. The failure simply disappears.

The solution

Single-pass recursive height check with early termination
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

Common follow-up questions