• Calculate leftHeight = getHeight(node.left).
• Calculate rightHeight = getHeight(node.right).
• If abs(leftHeight - rightHeight) > 1, return false.
• Otherwise, return isBalanced(node.left) && isBalanced(node.right).

Pseudo-code

text
function getHeight(node):
    if node is null: return 0
    return max(getHeight(node.left), getHeight(node.right)) + 1

function isBalanced(node):
    if node is null: return true
    if abs(getHeight(node.left) - getHeight(node.right)) > 1:
        return false
    return isBalanced(node.left) AND isBalanced(node.right)

Why this fails (Efficiency)

The time complexity of this approach is $O(N^2)$ in the worst case (a skewed tree). This occurs because getHeight is called repeatedly for the same nodes. For a node at depth $k$, getHeight visits it $k$ times (once for each ancestor's check). While this might pass the constraint of 5000 nodes, it is computationally redundant and demonstrates a lack of understanding regarding efficient tree traversals.

Core Insight for Balanced Binary Tree

The key intuition to optimizing the LeetCode 110 solution is to eliminate redundant height calculations. Instead of calculating height from the top down, we can compute it from the bottom up.

In a Postorder Traversal (Left, Right, Root), we visit a node only after visiting its children. This allows us to pass the height of the children up to the parent. However, we need to convey two pieces of information:

1. The height of the subtree rooted at the current node.
2. Whether the subtree is balanced.

We can combine these into a single integer return value. If a subtree is balanced, we return its actual height (a non-negative integer). If a subtree is unbalanced, we return a sentinel error code (e.g., -1).

Visual Description: Imagine the recursion tree expanding until it hits the null leaves. These leaves return a height of 0 to their parents. As the recursion unwinds (moves back up the stack), each parent node receives the heights of its left and right children. The parent immediately compares these two values. If the difference is greater than 1, or if either child reported an error (-1), the parent stops processing and passes -1 further up the chain. This effectively "short-circuits" the logic for that path, propagating the failure signal to the root.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

We implement a helper function (often named dfs or checkHeight) that performs the postorder traversal.

1. Base Case: If the current node is null, its height is 0. This is a balanced state.
2. Recursive Step (Left): Recursively call the function on the left child.
   • Constraint Check: If the left child returns -1 (indicating it is unbalanced), immediately return -1 to propagate the error.
3. Recursive Step (Right): Recursively call the function on the right child.
   • Constraint Check: If the right child returns -1, immediately return -1.
4. Current Node Logic:
   • Calculate the absolute difference between the left and right heights.
   • If the difference is greater than 1, the current subtree is unbalanced. Return -1.
   • Otherwise, the current subtree is balanced. Return the height of the current node, which is max(left_height, right_height) + 1.
5. Final Result: In the main function, check if the helper function returns -1. If it does, the tree is not balanced. Otherwise, it is.

Execution Flow

Let's trace the algorithm on root = [1, 2, 3, 4, 5, null, null] (where 4 and 5 are children of 2).

1. Start at Root (1): Call dfs(1).
2. Traverse Left to Node (2): Call dfs(2).
3. Traverse Left to Node (4): Call dfs(4).
   • dfs(4.left) (null) returns 0.
   • dfs(4.right) (null) returns 0.
   • Node 4 checks abs(0-0) <= 1. Returns max(0,0) + 1 = 1.
4. Traverse Right to Node (5): Call dfs(5).
   • dfs(5.left) (null) returns 0.
   • dfs(5.right) (null) returns 0.
   • Node 5 checks abs(0-0) <= 1. Returns max(0,0) + 1 = 1.
5. Process Node (2):
   • Receives left = 1 (from Node 4), right = 1 (from Node 5).
   • Checks abs(1-1) <= 1. Returns max(1,1) + 1 = 2.
6. Traverse Right to Node (3): Call dfs(3).
   • Children are null. Returns 1.
7. Process Root (1):
   • Receives left = 2 (from Node 2), right = 1 (from Node 3).
   • Checks abs(2-1) <= 1. This is true.
   • Returns max(2,1) + 1 = 3.
8. Result: The initial call returned 3 (not -1), so the tree is balanced.

Proof of Correctness

The correctness relies on the inductive property of the postorder traversal.

• Base Case: An empty tree (null) is balanced by definition.
• Inductive Step: For any node $N$, if the left subtree is balanced and returns height $H_L$, and the right subtree is balanced and returns height $H_R$, then the tree rooted at $N$ is balanced if and only if $|H_L - H_R| \le 1$.
• The algorithm enforces this condition at every single node. If the condition fails at any node, -1 is returned. Since -1 propagates strictly upwards, the root will eventually receive -1 if any violation exists in the entire tree structure.

Reference Implementation

C++ Solution for LeetCode 110

cpp
/**
 * 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 {
public:
    bool isBalanced(TreeNode* root) {
        return checkHeight(root) != -1;
    }

private:
    // Returns height of subtree if balanced, or -1 if unbalanced
    int checkHeight(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

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

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

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

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

Java Solution for LeetCode 110

java
/**
 * 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 dfsHeight(root) != -1;
    }

    // Returns the height of the tree if balanced, otherwise -1
    private int dfsHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

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

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

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

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

Python Solution for LeetCode 110

python
# 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:
        return self._check_height(root) != -1

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

• Mistake: Checking abs(height(root.left) - height(root.right)) <= 1 only at the root.
• Why: The problem states every node must be balanced. A tree can be balanced at the root (e.g., left height 5, right height 5) but have a severely unbalanced subtree deep inside.
• Consequence: The solution will return true for invalid trees (Incorrectness).

Q: Why do we return -1? Can we use a boolean?

• Mistake: Trying to return a boolean true/false from the recursive function while also needing to track height.
• Why: You need two pieces of data: the height (int) and the validity (bool). Returning just a boolean loses the height information required for the parent's calculation.
• Consequence: You would need a global variable or a custom class/pair return type, which adds unnecessary complexity compared to using -1 as a sentinel value.