Balanced Binary Tree

Easy Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazonMicrosoftMeta

Problem Description

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Examples

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

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

Combined DFS Height and Balance Checking

A naive solution computes height for every node, leading to O(n log n) or O(n²) time complexity. To do this in O(n) time, we can combine height calculation and balance validation in a single bottom-up DFS. We write a helper function that returns the height of the node, or -1 if any subtree is unbalanced:

If the node is null, return 0.
Recursively find the height of the left child (left_h). If it returned -1, return -1 immediately.
Recursively find the height of the right child (right_h). If it returned -1, return -1 immediately.
If the difference between left_h and right_h is greater than 1: abs(left_h - right_h) > 1, the tree is unbalanced; return -1.
Otherwise, return the actual height: 1 + max(left_h, right_h).

Solution 1: Bottom-Up DFS Validation

Perform bottom-up depth checking, returning -1 immediately if subtrees are unbalanced.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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

    private int checkHeight(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) return -1; // left subtree is unbalanced

        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) return -1; // right subtree is unbalanced

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // current node is unbalanced
        }

        return 1 + Math.max(leftHeight, rightHeight); // return height
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        
        def check_height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
                
            left_height = check_height(node.left)
            if left_height == -1:
                return -1
                
            right_height = check_height(node.right)
            if right_height == -1:
                return -1
                
            if abs(left_height - right_height) > 1:
                return -1
                
            return 1 + max(left_height, right_height)

        return check_height(root) != -1

#include <algorithm>
#include <cmath>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
private:
    int checkHeight(TreeNode* node) {
        if (!node) return 0;

        int leftHeight = checkHeight(node->left);
        if (leftHeight == -1) return -1;

        int rightHeight = checkHeight(node->right);
        if (rightHeight == -1) return -1;

        if (std::abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        return 1 + std::max(leftHeight, rightHeight);
    }

public:
    bool isBalanced(TreeNode* root) {
        return checkHeight(root) != -1;
    }
};

Complexity Analysis

Time Complexity: O(n) because we visit every node in the binary tree at most once.
Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.