Is every node's left and right height within one?

Trees Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
def h(level: list[int | None], i: int = 0) -> int:
    if i >= len(level) or level[i] is None:
        return 0
    return 1 + max(h(level, 2 * i + 1), h(level, 2 * i + 2))

level = [1, 2, 2, 3, None, None, None, 4]
print(h(level, 1), h(level, 2))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3 1

Right: the left side goes 2, 3, 4; the right side is a single node.

A gap of 2 between the two sides means the root is out of balance, even though no node has more than one child below it on the right.

Why not the others?
  • B 2 1. Node 4 at position 7 is the left child of 3, adding one more level.
  • C 3 3. The right child 2 has no children here.

30-second answer

Compute heights bottom-up and fail fast: return the height when a subtree is fine, or a sentinel (-1) as soon as any node is out of balance. One post-order pass, O(n) time, O(h) stack.

Practise saying it · 45 s. No recording, just a timer

Explain the balanced-height check in one pass.

Say your answer out loud, then check which of these points you covered:

  • Heights bottom-up
  • Fail-fast sentinel
  • O(n)

Deep dive

Calling height() separately at every node is O(n log n) on balanced trees and O(n²) on chains.

The sentinel trick merges two answers (height and 'ok') into one return value; a tuple is clearer if you prefer.

This is the property AVL trees maintain after every insert.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def within_one(root: Node | None) -> bool:
    def height(sub: Node | None) -> int:
        if sub is None:
            return 0
        left = height(sub.left)
        right = height(sub.right)
        if left < 0 or right < 0 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return height(root) >= 0

Common mistakes

  • Checking the balance only at the root.
  • Forgetting to propagate the failure sentinel upward.

Senior take & follow-ups

Mention the O(n²) version and why yours is O(n). That contrast is what the question tests.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why do self-balancing trees matter?

    Show hint

    They keep height O(log n), so search and insert stay O(log n).

  2. How would you rebalance?

    Show hint

    AVL rotations, or rebuild from the sorted in-order list by taking middles.

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.