110. Balanced Binary Tree

Checking if a tree is balanced is a fundamental skill frequently tested by giants like Google, Meta, and Amazon. It evaluates your grasp of tree traversals and your ability to optimize recursive depth-first search (DFS) to avoid redundant computations.

Problem statement

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

Constraints:

• The number of nodes in the tree is in the range $[0,5000]$.
• $−10^4 \leq$ Node.val $\leq 10^4$

Examples

Intuition

For a tree to be balanced, every single node must satisfy the height constraint. If we find even one node where the left and right subtree heights differ by more than $1$, the entire tree is “poisoned” and becomes unbalanced.

Instead of checking balance at each node independently (which would require re-calculating heights over and over), we can combine the height calculation and the balance check into one single post-order traversal.

Naive approach

In a naive approach, we treat the “balance check” and the “height calculation” as two separate tasks. For every node in the tree, we perform a three-part check:

1. Calculate the height of the left subtree using a helper function.
2. Calculate the height of the right subtree using the same helper function.
3. If the difference is $\leq 1$, we then recursively call the balance check on the left and right children.

The drawback: This approach is inefficient because it recalculates the height of the same nodes multiple times. When we check the root, we visit all nodes. When we move to the root’s children, we visit almost all nodes again.

Time complexity: In the best case of a balanced binary tree, the time complexity is $O(n \log n)$ because computing heights requires $O(n)$ work at each level and there are $\log n$ levels in total, resulting in $n \times logn$ operations. In contrast, the worst case occurs for a skewed tree that resembles a linked list, where height calculations repeat for nearly every node, leading to $n+(n−1)+(n−2)+⋯+1n + (n−1) + (n−2) + \dots + 1$ operations, which simplifies to a quadratic time complexity of $O(n^2)$.

Space complexity: $O(n)$ due to the recursive call stack.

Optimized approach using Depth First Search

Unlike the naive version, which checks balance from the top down, this method works bottom-up. It calculates the height while simultaneously checking for balance, using a sentinel value $(−1)$ to “short-circuit” the recursion as soon as an imbalance is found.

Step-by-step algorithm

Here’s the detailed algorithm that we’ll use to solve the given problem:

1. Initialize: Define a helper function, checkHeight(node), that returns the height of the tree if it is balanced, or $−1$ if it is not.
2. Base case: If the node is None, return $0$ (height of an empty tree).
3. Left/right check: Recursively call checkHeight on the left and right children.
   1. If any child returns $−1$, immediately propagate $−1$ up to the parent.
   2. Calculate abs(leftHeight - rightHeight). If it’s greater than $−1$, return $−1$.
4. If balanced, return the actual height: 1 + max(leftHeight, rightHeight).

Code implementation

Let’s look at the code for this solution below:

from collections import deque

# 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: TreeNode) -> bool:
        # Optimized Bottom-Up DFS
        def checkHeight(node):
            if not node:
                return 0
            
            # 1. Check left subtree
            leftHeight = checkHeight(node.left)
            if leftHeight == -1: 
                return -1
            
            # 2. Check right subtree
            rightHeight = checkHeight(node.right)
            if rightHeight == -1: 
                return -1
            
            # 3. Check current node balance
            if abs(leftHeight - rightHeight) > 1:
                return -1
            
            # 4. Return height if balanced
            return 1 + max(leftHeight, rightHeight)
        
        return checkHeight(root) != -1

# Not related to code: Helper function for pretty print
def treeToListStr(root):
    if not root:
        return "[]"
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append("null")

    while result and result[-1] == "null":
        result.pop()
        
    return "[" + ", ".join(map(str, result)) + "]"

def main():
    sol = Solution()
    
    # Test Case 1: The "Zig-Zag" Unbalanced (Left-Right-Left)
    # 1 -> 2 (left) -> 3 (right) -> 4 (left)
    tc1 = TreeNode(1, TreeNode(2, None, TreeNode(3, TreeNode(4))))
    
    # Test Case 2: Perfectly Balanced Full Tree
    #       1
    #     /   \
    #    2     3
    #   / \   / \
    #  4   5 6   7
    tc2 = TreeNode(1, 
                   TreeNode(2, TreeNode(4), TreeNode(5)), 
                   TreeNode(3, TreeNode(6), TreeNode(7)))
    
    # Test Case 3: The "Deep Imbalance" 
    # Balanced at the root level, but a subtree deep down is unbalanced
    # [1, 2, 2, 3, 3, 3, 3, 4, 4] -> Node 3 has a left height of 2 and right 0
    tc3 = TreeNode(1,
                   TreeNode(2, TreeNode(3, TreeNode(4), TreeNode(4)), TreeNode(3)),
                   TreeNode(2, TreeNode(3), TreeNode(3)))
    
    # Test Case 4: Left-Heavy but Balanced (Height diff is exactly 1)
    tc4 = TreeNode(10, TreeNode(5, TreeNode(2), None), TreeNode(15))
    
    # Test Case 5: The "Single Wing" (Unbalanced)
    # Root has a right child, but that child has a very deep left subtree
    tc5 = TreeNode(1, None, TreeNode(2, TreeNode(3, TreeNode(4))))

    testCases = [tc1, tc2, tc3, tc4, tc5]
    
    for i, root in enumerate(testCases, 1):
        input_display = treeToListStr(root)
        output = sol.isBalanced(root)
        
        print(f"{i}.  Input tree: {input_display}")
        print(f"    Output: {output}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

In our optimized bottom-up approach, we traverse each node exactly once. Because we use a post-order traversal (Left $\rightarrow$ Right $\rightarrow$ Root), we compute the balance of every subtree in a single pass.

• Every operation inside the recursive call, calculating the absolute difference, performing comparisons, and picking a maximum is $O(1)$.
• As we visit $n$ nodes and perform $O(1)$ work at each, the total time is $O(n)$.

Overall, the time complexity of the solution is $O(n)$.

Space complexity

The space complexity is determined by the maximum depth of the recursion stack.

• Best case (balanced tree): For a perfectly balanced tree, the height $h$ is $\log n$. The stack will only ever be as deep as the logarithmic height of the tree: $O(\log n)$.
• Worst case (skewed tree): In a “degenerate” or skewed tree (where the tree resembles a linked list), the height $h$ becomes $n$. The recursion must go $n$ levels deep before reaching a base case, resulting in $O(n)$.

Overall, the space complexity of the solution is $O(n)$.

Common pitfalls and interview tips

• The Root-only trap: Many candidates check if the root’s left and right heights differ by $1$ and stop there. Remember: every node must be balanced. A single deep branch far down the tree can make the entire structure unbalanced.
• Early exit: Don’t keep calculating heights once an imbalance is found. Use the $−1$ sentinel value to “short-circuit” the recursion and return immediately.
• Empty trees: Always ask or clarify how an empty tree should be handled. Usually, None is considered balanced.