Balanced Binary Tree

Description

Given the root of a binary tree, determine whether the tree is height-balanced.

A binary tree is considered height-balanced if, for every node in the tree, the absolute difference between the heights of its left subtree and its right subtree is at most 1.

The height of a node is the number of edges on the longest path from that node down to a leaf. A null (empty) subtree has height 0.

Return true if the tree is height-balanced, and false otherwise.

Examples

Example 1

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

Output: true

Explanation: The tree looks like this:

At node 3: left subtree height = 1 (just node 9), right subtree height = 2 (node 20 with children 15 and 7). The difference |1 − 2| = 1 ≤ 1. At node 20: left height = 1 (node 15), right height = 1 (node 7). Difference = 0. At node 9: both subtrees are empty, difference = 0. Every node satisfies the balance condition, so the tree is balanced.

Example 2

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

Output: false

Explanation: The tree looks like this:

At the root node 1: left subtree height = 3, right subtree height = 1. The difference |3 − 1| = 2 > 1. Since this exceeds the allowed difference of 1, the tree is not balanced.

Example 3

Input: root = []

Output: true

Explanation: An empty tree is trivially height-balanced because there are no nodes to violate the balance condition.

Constraints

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

Editorial

Brute Force - Top-Down Height Checking

Intuition

The definition of a balanced tree directly suggests an approach: for every node, check whether the heights of its left and right subtrees differ by more than one.

Imagine you are a building inspector who must verify that no floor in a building is lopsided. You start at the roof and, for every floor, you walk all the way down the left staircase to count the steps, then walk all the way down the right staircase to count those steps, and compare. If they differ by more than one, the building fails inspection. After checking one floor, you go down to the next floor and repeat the same full staircase walks.

The problem with this approach is that you are re-walking the same staircases many times. When the inspector checks the roof, they walk down to the basement through every floor. Then when they check the second floor, they walk down the same stairs they already walked. This redundant walking is exactly why the brute force is slow — it recomputes subtree heights at every level of the tree.

Step-by-Step Explanation

Let's trace through Example 1: root = [3, 9, 20, null, null, 15, 7]

Step 1: Begin at the root node 3. We need to compute the height of its left and right subtrees.

Step 2: Compute height of left subtree of node 3. Visit node 9 — it has no children, so height = 1.

Step 3: Compute height of right subtree of node 3. Visit node 20, which has children.

Step 4: To find height(20), visit its left child node 15 — a leaf, height = 1.

Step 5: Visit right child of node 20: node 7 — a leaf, height = 1. So height(20) = 1 + max(1, 1) = 2. Therefore, the right subtree of root has height 2.

Step 6: Compare at root node 3: leftHeight = 1, rightHeight = 2, |1 − 2| = 1 ≤ 1. Node 3 passes the balance check. Now recurse to check children.

Step 7: Check isBalanced(9). Node 9 is a leaf: leftHeight = 0, rightHeight = 0. |0 − 0| = 0 ≤ 1. Balanced.

Step 8: Check isBalanced(20). We need height(15) and height(7) — but we already visited these nodes during the root's height computation! This is the redundancy. height(15) = 1, height(7) = 1.

Step 9: Compare at node 20: |1 − 1| = 0 ≤ 1. Balanced.

Step 10: Check leaf nodes 15 and 7 — trivially balanced.

Step 11: All nodes pass the balance check. Return true. Note that nodes 15 and 7 were visited multiple times due to repeated height computations.

Brute Force — Top-Down Repeated Height Computation — Watch how the top-down approach re-visits nodes during height computation at every level, leading to redundant work.

Algorithm

Define a helper function height(node) that returns the height of the subtree rooted at node:
- If node is null, return 0
- Otherwise, return 1 + max(height(node.left), height(node.right))
For the main function isBalanced(root):
- If root is null, return true (empty tree is balanced)
- Compute leftHeight = height(root.left)
- Compute rightHeight = height(root.right)
- If |leftHeight − rightHeight| > 1, return false
- Recursively return isBalanced(root.left) AND isBalanced(root.right)

Code

class Solution {
public:
    int height(TreeNode* node) {
        if (node == nullptr) return 0;
        return 1 + max(height(node->left), height(node->right));
    }

    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;

        int leftHeight = height(root->left);
        int rightHeight = height(root->right);

        if (abs(leftHeight - rightHeight) > 1) return false;

        return isBalanced(root->left) && isBalanced(root->right);
    }
};

class Solution:
    def height(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        return 1 + max(self.height(node.left), self.height(node.right))

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        left_height = self.height(root.left)
        right_height = self.height(root.right)

        if abs(left_height - right_height) > 1:
            return False

        return self.isBalanced(root.left) and self.isBalanced(root.right)

class Solution {
    public int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        if (Math.abs(leftHeight - rightHeight) > 1) return false;

        return isBalanced(root.left) && isBalanced(root.right);
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n nodes, we call height() which traverses its entire subtree. In a balanced tree this gives O(n log n), but in the worst case — a skewed tree (essentially a linked list) — the root's height call visits all n nodes, the next level visits n−1, and so on, summing to n + (n−1) + (n−2) + ... + 1 = O(n²).

Space Complexity: O(h) where h is the height of the tree

The space is used by the recursion stack. In the worst case (skewed tree), h = n, so space is O(n). For a balanced tree, h = log n, so space is O(log n).

Why This Approach Is Not Efficient

The brute force approach has a fundamental flaw: redundant computation. When we call isBalanced(root), we compute height(root.left) which traverses the entire left subtree. But then isBalanced recursively calls isBalanced(root.left), which again calls height() on the left subtree's children — re-traversing nodes we already visited.

With n up to 5000 and a potentially skewed tree, the O(n²) worst case means up to ~12.5 million operations. While this might pass for the given constraints, the approach is wasteful.

The key insight is that height computation and balance checking can be combined into a single traversal. Instead of computing height first and checking balance separately, we can do both at once: as we compute the height of a subtree from the bottom up, we simultaneously verify the balance condition. If any subtree is unbalanced, we propagate a failure signal (like −1) upward, short-circuiting the rest of the computation. This eliminates all redundant traversals and reduces the time to O(n).

Optimal Approach - Bottom-Up DFS with Early Termination

Intuition

Instead of checking balance from the top down (which re-computes heights), we can work from the bottom up. Think of it as a chain of workers in a building:

Each worker on each floor measures the height of their section and reports upward. If any worker finds that their left and right sections differ by more than one floor, they shout "UNBALANCED!" and the message propagates all the way to the top without anyone else needing to do additional measurements.

Technically, we write a single recursive function that returns the height of the subtree if it's balanced, or −1 if it's unbalanced. The −1 acts as a sentinel value that propagates upward: once any subtree returns −1, all ancestor calls immediately return −1 without further work.

This way, every node is visited exactly once. We compute its height and verify its balance in the same call, yielding O(n) time.

Step-by-Step Explanation

Let's trace through Example 2: root = [1, 2, 2, 3, 3, null, null, 4, 4] (an unbalanced tree)

Step 1: Start bottom-up DFS from the root. The recursion goes deep-left first before processing any node.

Step 2: Reach the deepest left leaf: node 4 (left child of left-3). It has no children. Return height = 1.

Step 3: Visit node 4 (right child of left-3). Also a leaf. Return height = 1. Both children of left-3 are resolved.

Step 4: Process node 3 (left child of 2): leftHeight = 1, rightHeight = 1. |1 − 1| = 0 ≤ 1. Balanced here. Return height = 1 + max(1, 1) = 2.

Step 5: Visit node 3 (right child of 2). It's a leaf. Return height = 1. Both children of node 2 are resolved.

Step 6: Process node 2 (left child of root): leftHeight = 2 (from step 4), rightHeight = 1 (from step 5). |2 − 1| = 1 ≤ 1. Still balanced. Return height = 1 + max(2, 1) = 3.

Step 7: Visit node 2 (right child of root). It's a leaf. Return height = 1. Both children of root are resolved.

Step 8: Process root node 1: leftHeight = 3 (deep left subtree), rightHeight = 1 (single right node). |3 − 1| = 2 > 1. UNBALANCED! The left side is much deeper than the right.

Step 9: Return −1 (sentinel for unbalanced). Final answer: false. We visited each of the 7 nodes exactly once — O(n) time with zero redundancy.

Bottom-Up DFS — Single Pass Balance Detection — Watch how the bottom-up approach processes each node exactly once, combining height computation with balance verification, and detects imbalance at the root.

Algorithm

Define a helper function checkHeight(node):
- If node is null, return 0
- Recursively compute leftHeight = checkHeight(node.left)
- If leftHeight == −1, return −1 (left subtree is unbalanced, propagate failure)
- Recursively compute rightHeight = checkHeight(node.right)
- If rightHeight == −1, return −1 (right subtree is unbalanced, propagate failure)
- If |leftHeight − rightHeight| > 1, return −1 (current node is unbalanced)
- Otherwise, return 1 + max(leftHeight, rightHeight)
In the main function: return checkHeight(root) ≠ −1

Code

class Solution {
public:
    int checkHeight(TreeNode* node) {
        if (node == nullptr) return 0;

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

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

        if (abs(leftHeight - rightHeight) > 1) return -1;

        return 1 + max(leftHeight, rightHeight);
    }

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

class Solution:
    def checkHeight(self, node: Optional[TreeNode]) -> int:
        if not node:
            return 0

        left_height = self.checkHeight(node.left)
        if left_height == -1:
            return -1

        right_height = self.checkHeight(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1

        return 1 + max(left_height, right_height)

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self.checkHeight(root) != -1

class Solution {
    public int checkHeight(TreeNode node) {
        if (node == null) return 0;

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

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

        if (Math.abs(leftHeight - rightHeight) > 1) return -1;

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

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

Complexity Analysis

Time Complexity: O(n)

Each node is visited exactly once. At each node, we do O(1) work: compare heights and decide whether to return −1 or the computed height. The total work across all n nodes is therefore O(n).

Space Complexity: O(h) where h is the height of the tree

The recursion stack depth equals the height of the tree. In the worst case (a completely skewed tree), h = n, giving O(n) space. For a balanced tree, h = log n, giving O(log n) space.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Balanced Binary Tree

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force - Top-Down Height Checking

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Bottom-Up DFS with Early Termination

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis