Check If a Tree Is Balanced | Dataford Interview Questions

MSCI analytics services can represent hierarchical structures as binary trees. Given the root of a binary tree, determine whether the tree is height-balanced.

A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by no more than 1.

Formal Specification

Implement is_balanced(root), where root is either None or a nested dictionary with this structure:

value: an integer node value
left: another node dictionary or None
right: another node dictionary or None

Return True if the tree is height-balanced, otherwise return False. The values do not affect the result.

Your solution should avoid repeatedly calculating subtree heights. Use a depth-first strategy that detects imbalance while returning height information to each parent.

Constraints

The tree contains between 0 and 10^5 nodes.
Each node has at most two children.
Node values are integers in the range [-10^9, 10^9].
None represents an empty subtree.

Function Signature

def is_balanced(root):

Your question is Check If a Tree Is Balanced. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem