1. Understanding the Problem

You are given the root of a binary tree. Your task is to determine if it is height-balanced.

What is a Height-Balanced Tree?

In computer science, a height-balanced binary tree is defined by a very specific rule: the depth (height) of the two subtrees of every node never differs by more than 1.

A Quick Example

Imagine a tree where the root has a left branch that goes down 3 levels, and a right branch that goes down 2 levels. The difference is 3 - 2 = 1. This node is balanced. However, if the left branch went down 4 levels and the right branch went down 2 levels, the difference would be 2. The tree would instantly be declared unbalanced.

2. The Naive Approach: Top-Down (What to Avoid)

The most intuitive way to solve this is to write a function that calculates the height of a tree. Then, starting at the root, you calculate the height of the left side, the height of the right side, and see if the difference is greater than 1.

If it is fine, you move down to the left child and repeat the exact same process, then move to the right child and repeat.

Trade-off Analysis

While logically correct, this "Top-Down" approach is extremely inefficient:

• Time Complexity: O(N²) in the worst case. Because you are recalculating the height of the same lower nodes over and over again as you move down the tree, you are doing massive amounts of duplicate work.

3. The Optimal Approach: Bottom-Up DFS

To pass a senior-level technical interview, we must achieve an O(N) runtime. We can do this by eliminating the duplicate work. Instead of starting at the top and looking down, we use a Bottom-Up Depth-First Search (DFS).

We send our recursive function all the way down to the bottom leaves of the tree first. As the function travels back up the tree, it carries the height of the branches with it. This means every node's height is calculated exactly once.

The "Trick": We need our recursive function to return the height of the tree, but we also need it to tell us if the tree is unbalanced. To do both, we use a special flag: if a subtree is ever found to be unbalanced, we immediately return -1. If any parent node sees a -1 coming from its children, it knows the tree is broken and just passes the -1 higher up.

4. The Logic Step-by-Step

1. Create a recursive helper function called dfs that takes a node as its argument.
2. The Base Case: If the node is null (we reached the bottom), return a height of 0.
3. The Recursive Leaps:
   • Call dfs on the left child to get the left_height.
   • If left_height is -1, immediately return -1 (the left side is unbalanced, so the whole tree is unbalanced).
   • Call dfs on the right child to get the right_height.
   • If right_height is -1, immediately return -1.
4. The Balance Check: Calculate the absolute difference between left_height and right_height.
   • If the difference is greater than 1, return -1.
   • Otherwise, the tree is balanced at this node! Return its true height: 1 + max(left_height, right_height).
5. Finally, in your main function, call the helper on the root. If it returns -1, return False. Otherwise, return True.

5. Complexity Analysis

• Time Complexity: O(N) — We visit every single node in the tree exactly one time. Once we calculate a node's height, we never calculate it again.
• Space Complexity: O(H) — Where H is the height of the tree. This is the memory used by the recursive call stack. In a perfectly balanced tree, this is O(log N). In a completely unbalanced tree, it is O(N).

6. Code Implementations

Expand the sections below to see the optimal O(N) Bottom-Up implementations across different languages.

# 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) -> bool:
        
        def dfs(node):
            # Base case: an empty tree has height 0
            if not node:
                return 0
                
            # Check left subtree
            left_height = dfs(node.left)
            if left_height == -1:
                return -1
                
            # Check right subtree
            right_height = dfs(node.right)
            if right_height == -1:
                return -1
                
            # If the difference in heights is > 1, it's unbalanced
            if abs(left_height - right_height) > 1:
                return -1
                
            # If balanced, return the actual height of this node
            return 1 + max(left_height, right_height)
            
        # If dfs returns -1, it means the tree is unbalanced
        return dfs(root) != -1

/**
 * 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 dfs(root) != -1;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = dfs(node.left);
        if (leftHeight == -1) {
            return -1; // Left subtree is unbalanced
        }
        
        int rightHeight = dfs(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);
    }
}

#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 {
public:
    bool isBalanced(TreeNode* root) {
        return dfs(root) != -1;
    }
    
private:
    int dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        int leftHeight = dfs(node->left);
        if (leftHeight == -1) {
            return -1;
        }
        
        int rightHeight = dfs(node->right);
        if (rightHeight == -1) {
            return -1;
        }
        
        if (std::abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        
        return 1 + std::max(leftHeight, rightHeight);
    }
};

7. Conclusion: You Are Ready

You have just mastered a vital tree optimization technique. By realizing that you can pass state upward from the bottom leaves, you successfully avoided the dreaded O(N²) trap. Using a dummy value like -1 to act as an error flag is a highly common and professional pattern in software engineering. Keep this bottom-up DFS logic in your mind—it is the exact same pattern used for other advanced problems like "Diameter of a Binary Tree". You are one step closer to dominating your algorithmic interviews!