A large-scale system manages hierarchical data structures such as:
- file directories
- organizational charts
- dependency trees
For optimal performance, the system ensures that its tree structures remain balanced, so that operations like search, insertion, and traversal remain efficient.
A tree is considered height-balanced if:
For every node, the height difference between its left and right subtrees is not more than 1
If the tree becomes unbalanced, operations may degrade from efficient O(log n) to slower O(n) time.
The system needs a validation check to ensure that the tree remains balanced at all times.
This is a common coding interview problem frequently asked in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given the root of a binary tree, return:
true if the tree is height-balancedfalse otherwise
Input Format
root: root node of a binary tree
Each node:
TreeNode { int val; TreeNode left; TreeNode right;}
Output Format
Examples
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Explanation: Height difference at every node ≤ 1
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: Left subtree is too deep → imbalance > 1
Example 3:
Input: root = []
Output: true