Balanced Binary Tree

Easy · Trees

You are given the root of a binary tree. Determine whether the tree is height-balanced, meaning that for every single node in the tree, the heights of its left and right subtrees never differ by more than one. Return true if this holds everywhere in the tree, and false otherwise.

Examples

Input:  root = [3,9,20,null,null,15,7]
Output: true
Why:    Every node's two subtrees differ in height by at most 1, so the tree is balanced.

Input:  root = [1,2,2,3,3,null,null,4,4]
Output: false
Why:    The left subtree rooted at the second node 2 has height 3 while the right subtree has height 1, a gap greater than 1.

Input:  root = []
Output: true
Why:    An empty tree has no node violating the height rule, so it is considered balanced.

Constraints

0 <= number of nodes <= 5000, -10^4 <= node value <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Balanced Binary Tree

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Balanced Binary Tree. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.