Balanced Binary Tree

Balanced Binary Tree (LeetCode 110) is a standard interview problem often associated with Spotify coding interviews, focusing on Tree, DFS, and Binary Tree concepts. It requires checking if a binary tree is height-balanced, where the height difference between left and right subtrees of every node is at most 1. This matches the tags and context from search results on Spotify engineer interviews.[1][2][3]

Problem Statement

Given the root of a binary tree, determine if it is height-balanced.
A binary tree is height-balanced if for every node, the absolute difference in heights between its left and right subtrees is at most 1.

• Implement using DFS (post-order traversal) to compute heights bottom-up while checking balance.
• Return true if balanced, false otherwise.[2][3]

Input/Output Examples

Example 1: Balanced Tree

Input:
3 / \ 9 20 / \ 15 7 Output: true
Explanation: All subtree height differences ≤ 1.[2]

Example 2: Unbalanced Tree

Input:
1 / \ 2 2 / \ 3 3 / 4 Output: false
Explanation: Node with value 2 has left height 0 and right height 2 (diff > 1).[2]

Example 3: Single Node

Input: [1]
Output: true
Explanation: Trivial case, balanced by definition.[2]

Constraints

• Number of nodes: 0 ≤ n ≤ 5,000
• Node values: -10^4 ≤ Node.val ≤ 10^4
• Tree may be empty (root = null).[2]