Command Palette

Search for a command to run...

Hectal
Problem 16.6 · Binary TreesEasy

Balanced Binary Tree

PatternTree DFS

What it teaches: Return a sentinel (−1) up the tree as soon as a subtree is unbalanced, keeping it O(n).

Practise it on judges as “Balanced Binary Tree”.

The problem

A tree is height-balanced if, at every node, the heights of the two subtrees differ by at most 1. Return whether the tree is balanced.

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

Constraints

  • 0 ≤ nodes ≤ 5000

Pattern clues in the wording

  • → A property checked at every node, using subtree heights

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean isBalanced(TreeNode root) {
        return true;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [3,9,20,null,null,15,7]
true
2
root = [1,2,2,3,3,null,null,4,4]
false
3
root = []
true

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Height or −1 · O(n)
1

Height or −1

Time O(n) Space O(h)

check(n): null → 0. If either child returns −1 or their heights differ by more than 1, return −1. Else return 1 + max.

Approach 1
class Solution {
    public boolean isBalanced(TreeNode root) {
        return check(root) != -1;
    }

    private int check(TreeNode n) {
        if (n == null) return 0;
        int l = check(n.left);
        if (l == -1) return -1;
        int r = check(n.right);
        if (r == -1 || Math.abs(l - r) > 1) return -1;
        return 1 + Math.max(l, r);
    }
}

Verdict: One pass with early exit.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Empty tree → true
  • Balanced at the root but not lower down

Mistakes people make

  • Checking balance only at the root.

Interview

Follow-up questions

Why do balanced trees matter?