Balanced Binary Tree | Dataford Interview Questions

Balanced Binary Tree

EasyPython

Problem

Binance may represent hierarchical structures such as referral or permission relationships as binary trees. Given a binary tree, determine whether it is height-balanced: at every node, the heights of its left and right subtrees differ by no more than one.

Use a single function that returns True for a balanced tree and False otherwise. The input tree is encoded recursively as [value, left, right], where left and right are either another encoded tree or null. An empty tree is represented by null. The node value can be any integer and does not affect balance.

Formal Specification

Input: root, a nested list or null. A non-empty node has the form [value, left, right].
Output: A boolean indicating whether the tree is height-balanced.

Your solution should avoid repeatedly calculating subtree heights, since that can make a skewed tree quadratic. Return as soon as an unbalanced subtree is detected.

Constraints

0 <= number of nodes <= 10^5
value is an integer in [-10^9, 10^9]
The encoded tree contains no cycles
The solution should run in linear time

Function Signature

def is_balanced(root):

Formal Specification

Input: root, a nested list or null. A non-empty node has the form [value, left, right].
Output: A boolean indicating whether the tree is height-balanced.

Your solution should avoid repeatedly calculating subtree heights, since that can make a skewed tree quadratic. Return as soon as an unbalanced subtree is detected.