easyTrees

Balanced Binary Tree

A tree is height-balanced if the depths of the left and right subtrees differ by at most one at every node. Check this property.

LeetCode ↗

Work through the cases

3 examples

Input notation

A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree.

Expected result

true or false.

Case 1

Input

1 2 3

Expected output

true

Case 2

Input

1 2 null 3 null 4

Expected output

false

Case 3

Input

null

Expected output

true

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Computing left and right heights from scratch at every node revisits the same subtrees and can hit O(n^2); n ≤ 5000 is tight. Balance can be decided while computing height. A bottom-up pass returns the height, or a failure sentinel if a subtree is already unbalanced. One postorder walk answers both questions.

We define a function height(root) to calculate the height of a binary tree, with the following logic:

- If the binary tree root is null, return 0. - Otherwise, recursively calculate the heights of the left and right subtrees, denoted as l and r respectively. If either l or r is -1, or the absolute difference between l and r is greater than 1, then return -1. Otherwise, return max(l, r) + 1.

Therefore, if the function height(root) returns -1, it means the binary tree root is not balanced. Otherwise, it is balanced.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

/**
 * 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 height(root) >= 0;
    }

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

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.