#110 Balanced Binary Tree - Solution

The goal of #110 Balanced Binary Tree is to determine whether the height difference between the left and right subtrees of every node is at most one. A straightforward idea is to compute the height of each subtree and verify the balance condition at every node. However, repeatedly calculating subtree heights can lead to unnecessary work.

A more efficient strategy uses Depth-First Search (DFS) with a post-order traversal. Starting from the leaves, compute the height of each subtree and propagate the result upward. If at any node the difference between the left and right subtree heights exceeds one, the tree is not balanced. Many implementations return a special value (for example -1) to signal imbalance and stop further computation early.

This approach ensures each node is visited only once while checking both subtree heights and balance conditions simultaneously. The method is efficient and commonly expected in technical interviews.

Approach	Time Complexity	Space Complexity
Naive height check for each node	O(n^2)	O(h)
Optimized DFS with post-order traversal	O(n)	O(h)

Solutions (12)

Recursive Height Calculation

This approach involves recursively calculating the height of each subtree and checking if the subtrees are balanced by ensuring the difference in height is not more than one.

Time Complexity: O(N^2), where N is the number of nodes in the tree, as we recalculate the height of subtrees multiple times. Space Complexity: O(N) due to recursion stack.

C C++Java Python C#JavaScript

1function TreeNode(val) {
2    this.val = val;
3    this.left = this.right = null;
4}
5
6function isBalanced(root) {
7    if (root === null) return true;
8
9    function height(node) {
10        if (node === null) return 0;
11        return Math.max(height(node.left), height(node.right)) + 1;
12    }
13
14    const leftHeight = height(root.left);
15    const rightHeight = height(root.right);
16
17    return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
18}

Explanation

JavaScript uses a recursive function height to evaluate the height of nodes. The isBalanced function uses this information to ensure that subtree height differences are within acceptable range, checking recursively.

Optimized Recursive Approach

This optimized approach calculates the height and balance status of a tree in a single recursive function, thus avoiding recalculations by returning both height and balanced status in form of tuples or objects.

Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth.

C C++Java Python C#JavaScript

1public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public bool IsBalanced(TreeNode root) {
        return CheckBalance(root).balanced;
    }

    private (int height, bool balanced) CheckBalance(TreeNode node) {
        if (node == null) return (0, true);
        var left = CheckBalance(node.left);
        if (!left.balanced) return (0, false);
        var right = CheckBalance(node.right);
        if (!right.balanced) return (0, false);
        bool balanced = Math.Abs(left.height - right.height) <= 1;
        return (Math.Max(left.height, right.height) + 1, balanced);
    }
}