All problems

Balanced Binary Tree

Easy · tree dfs

You are given the root of a binary tree. The depth of a subtree is the number of nodes on the longest path from its top node down to a leaf; an empty subtree has depth 0.

A tree is balanced if, at every node, the depth of the left subtree and the depth of the right subtree differ by at most 1. Return true if the tree is balanced and false otherwise.

A tree with no nodes is balanced.

Examples

Example 1

Input: root = [4, 2, 6, 1, 3, 5, 7]

Output: true

Every node has either two children of equal depth or no children.

Example 2

Input: root = [1, 2, null, 3]

Output: false

The root has a left subtree of depth 2 and an empty right subtree, a difference of 2.

Example 3

Input: root = [1, 2, 2, 3, null, null, 3, 4, null, null, 4]

Output: false

Both sides of the root have depth 3, so the root looks fine. The trouble is lower down: the left child of the root has a left subtree of depth 2 and nothing on its right.

Constraints