How do you approach Balanced Binary Tree?

Computing the height inside an isBalanced check that also recurses gives O(n^2) - each node's height is recomputed for every ancestor.

What is the time complexity of Balanced Binary Tree?

Time complexity: O(n) - each node visited once.. Space complexity: O(h) for the recursion stack..

What are common mistakes on Balanced Binary Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Balanced Binary Tree

EasyData Structures

Description

Given a binary tree, determine whether it is **height-balanced**: for every node, the heights of its two subtrees differ by at most 1. The tree is given as a **level-order array with explicit nulls**, where the children of index `i` sit at `2i + 1` and `2i + 2`. An empty array is an empty tree.

Example 1

Input: root = [3,9,20,null,null,15,7]

Output: true

Example 2

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

Output: false

Example 3

Input: root = []

Output: true

Constraints

- 0 <= number of nodes <= 5000 - The naive solution recomputes height at every node, which is O(n^2). Aim for O(n).

Balanced Binary Tree: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Computing the height inside an isBalanced check that also recurses gives O(n^2) - each node's height is recomputed for every ancestor.
Write ONE recursive function that returns the height and detects imbalance on the way back up.
Use a sentinel: return -1 to mean 'a subtree below here is unbalanced', and propagate it immediately without further work.

The optimal approach

Show the approach: Compute height and balance in a single pass

The naive version asks "is the left balanced, is the right balanced, and do their heights differ by at most 1" - which calls a height function at every node, and that function walks the whole subtree. Heights get recomputed once per ancestor, so a skewed tree costs O(n^2).

The fix is to let one post-order traversal return both facts. Each call returns the subtree height, or a sentinel `-1` meaning "something below is unbalanced". A node that sees `-1` from either child propagates it straight up without inspecting anything else, so the whole tree is visited once.

The sentinel works because a real height is never negative, so there is no ambiguity between "unbalanced" and a legitimate value. Returning a tuple of (height, isBalanced) is equally correct and more explicit - worth mentioning in an interview as the readable alternative.

Time: O(n) - each node visited once.
Space: O(h) for the recursion stack.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

← Back to problems

Balanced Binary Tree

EasyData Structures

Description

Example 1

Input: root = [3,9,20,null,null,15,7]

Output: true

Example 2

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

Output: false

Example 3

Input: root = []

Output: true

Constraints

- 0 <= number of nodes <= 5000 - The naive solution recomputes height at every node, which is O(n^2). Aim for O(n).

Balanced Binary Tree: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Computing the height inside an isBalanced check that also recurses gives O(n^2) - each node's height is recomputed for every ancestor.
Write ONE recursive function that returns the height and detects imbalance on the way back up.
Use a sentinel: return -1 to mean 'a subtree below here is unbalanced', and propagate it immediately without further work.

The optimal approach

Show the approach: Compute height and balance in a single pass

Time: O(n) - each node visited once.
Space: O(h) for the recursion stack.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.