Balanced Binary Tree

Easy
1866.

Balanced Binary Tree

Balanced Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google, Microsoft and Bloomberg interviews.

Given the root of a binary tree, return true if it is height-balanced and false otherwise.

A tree is height-balanced when, at every node, the heights of the left and right subtrees differ by at most one. The height of an empty subtree is 0.

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
true
Explanation
At the root the subtrees have heights 1 and 2; every other node is also within one.

Example 2

Input
root = [1,2,2,3,3,null,null,4,4]
Output
false
Explanation
At the root the left subtree has height 3 and the right one height 1.

Example 3

Input
root = []
Output
true

Constraints

  • The number of nodes in the tree is in the range [0, 5000]
  • -10^4 <= Node.val <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Balanced Binary Tree — Solution in Python, Java & C++

Balanced Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Balanced Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google, Microsoft and Bloomberg interviews.

Problem statement

Given the root of a binary tree, return true if it is height-balanced and false otherwise.

A tree is height-balanced when, at every node, the heights of the left and right subtrees differ by at most one. The height of an empty subtree is 0.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: true
Explanation: At the root the subtrees have heights 1 and 2; every other node is also within one.

Example 2

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: At the root the left subtree has height 3 and the right one height 1.

Example 3

Input: root = []
Output: true

Constraints

  • The number of nodes in the tree is in the range [0, 5000]
  • -10^4 <= Node.val <= 10^4

Hints for Balanced Binary Tree

  1. Hint 1

    Checking the root alone is not enough — the condition must hold at every node.

  2. Hint 2

    Calling a height function at every node works but recomputes heights over and over: O(n^2) on a chain.

  3. Hint 3

    Compute heights bottom-up and let the helper return a sentinel such as -1 as soon as any subtree is unbalanced.

How to solve Balanced Binary Tree

One post-order walk can compute every subtree's height and check balance at the same time: a helper returns a node's height, or -1 if anything below it is already unbalanced, and the -1 propagates straight up.

Approach

  1. check(null) = 0.
  2. For a node, compute l = check(left); if it is -1 return -1. Do the same for r.
  3. If |l - r| > 1 return -1.
  4. Otherwise return 1 + max(l, r).
  5. The tree is balanced when check(root) != -1.

Why it works

Every node's balance condition is tested exactly when both of its subtree heights are known, so every node is checked, and a single failure anywhere forces -1 all the way to the root. Heights are each computed once, instead of once per ancestor.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth

Pitfalls

  • Comparing only the root's two subtree heights accepts trees like [1,2,2,3,null,null,3,4,null,null,4] that are unbalanced lower down.
  • The top-down version (height at every node) is O(n^2) on skewed trees.
  • An empty tree is balanced.

Reference solution

Python

from typing import Optional

def isBalanced(root: Optional[TreeNode]) -> bool:
    def check(node):
        if node is None:
            return 0
        l = check(node.left)
        if l < 0:
            return -1
        r = check(node.right)
        if r < 0 or abs(l - r) > 1:
            return -1
        return 1 + max(l, r)

    return check(root) >= 0

Java

public static boolean isBalanced(TreeNode root) {
    return balancedHeight(root) >= 0;
}

static int balancedHeight(TreeNode node) {
    if (node == null) return 0;
    int l = balancedHeight(node.left);
    if (l < 0) return -1;
    int r = balancedHeight(node.right);
    if (r < 0 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

C++

int balancedHeight(TreeNode* node) {
    if (!node) return 0;
    int l = balancedHeight(node->left);
    if (l < 0) return -1;
    int r = balancedHeight(node->right);
    if (r < 0 || abs(l - r) > 1) return -1;
    return 1 + max(l, r);
}

bool isBalanced(TreeNode* root) {
    return balancedHeight(root) >= 0;
}

JavaScript

var isBalanced = function(root) {
    return balancedHeight(root) >= 0;
};

var balancedHeight = function(node) {
    if (node === null) return 0;
    var l = balancedHeight(node.left);
    if (l < 0) return -1;
    var r = balancedHeight(node.right);
    if (r < 0 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals