Cracking The Coding Interview Together – Problem 4.4: Check Balanced Binary Tree

We've all encountered binary trees. They're fundamental, versatile, and seemingly straightforward. But what happens when a tree, designed for efficient lookups, starts to resemble a linked list? Its performance plummets, turning an elegant O(log N) operation into a sluggish O(N). This is the core conflict we face: ensuring our trees remain 'balanced' to deliver on their promise of efficiency.

The challenge lies not just in understanding what 'balanced' means, but in devising an algorithm that can verify this property efficiently across an entire tree. Today, we're going to tackle a classic problem that forces us to think deeply about tree traversals and recursive logic: checking if a binary tree is balanced. Our shared goal is to build a robust, efficient solution that you can confidently apply in your next technical interview or real-world system.

Problem Statement

Check Balanced: Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

The problem is deceptively simple on the surface: implement a function to check if a binary tree is balanced. The critical detail, however, lies in the precise definition of 'balanced' for this specific problem. A tree is considered balanced if, for every single node within the tree, the heights of its two subtrees (left and right) never differ by more than one. This isn't about the overall tree height, but a local property that must hold true at every level. We need to return a boolean indicating whether this condition is met for the entire tree.

Analyze the Problem Together

Let's dissect this. The constraint is clear:

abs(height(left_subtree) - height(right_subtree)) <= 1 for every node. This 'every node' clause is where the complexity hides. A naive approach might involve, for each node, recursively calculating the height of its left subtree and its right subtree. While this works, think about the redundancy. When we calculate the height of a node's left child, we're essentially re-calculating heights for all nodes in that left child's subtree. If we do this for every node, many subtrees will have their heights computed multiple times. This leads to an O(N log N) or even O(N^2) solution in the worst case, which isn't optimal.

The 'Aha!' moment here is realizing that we can combine the height calculation with the balance check. As we traverse the tree, we want to know two things about each subtree: its height, and whether it's balanced. If we can get both pieces of information in a single pass, we can avoid redundant computations. This suggests a recursive, depth-first approach where a function returns not just a boolean, but perhaps an integer representing height, with a special value indicating an unbalanced state.

Questions for the Interviewer

Before we dive into coding, a senior engineer always clarifies assumptions. Here are a few questions we'd ask:

• What should we return for an empty tree (a null root)? Typically, an empty tree is considered balanced, and its height is -1 (or 0, depending on convention). We'll assume it's balanced with a height of -1 for consistency with common tree height definitions.
• Are there any constraints on the node values or the size of the tree? While the values themselves don't affect balance, the size might influence performance expectations. For this problem, we'll assume a standard binary tree structure.
• Is this a Binary Search Tree (BST) or a general Binary Tree? The problem statement implies a general binary tree. If it were a BST, the balance property would be even more critical for search performance, but the checking algorithm remains the same.

Think About the Solution

Our high-level architecture will leverage recursion, specifically a Depth-First Search (DFS) approach. The core idea is to design a helper function that, for any given node, can tell us two things:

1. Is the subtree rooted at this node balanced?
2. What is the height of the subtree rooted at this node?

If at any point we discover an unbalanced subtree, we can immediately propagate this 'unbalanced' status up the call stack, short-circuiting further computations.

Let's define our helper function. It will take a TreeNode as input and return an integer. This integer will represent the height of the subtree. However, if the subtree is found to be unbalanced, we'll use a special sentinel value, like -1, to signal this.

Here's the flow:

• Base Case: If the node is null, it's balanced and has a height of -1.
• Recursive Step:
  • Recursively call the helper on the left child.
  • If the left subtree is unbalanced (returns -1), then the current tree is also unbalanced. Return -1.
  • Recursively call the helper on the right child.
  • If the right subtree is unbalanced (returns -1), then the current tree is also unbalanced. Return -1.
  • Now, we have the heights of the left and right subtrees. Check if their absolute difference is greater than 1. If it is, the current tree is unbalanced. Return -1.
  • If all checks pass, the current subtree is balanced. Its height is 1 + max(left_height, right_height). Return this height.

Write Code and Explain

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BalancedBinaryTree {

    /**
     * Main function to check if a binary tree is balanced.
     * It calls a helper function that returns the height or a special value (-1) if unbalanced.
     *
     * @param root The root of the binary tree.
     * @return True if the tree is balanced, false otherwise.
     */
    public boolean isBalanced(TreeNode root) {
        // An empty tree is considered balanced.
        if (root == null) {
            return true;
        }
        // If the helper function returns -1, it means the tree is unbalanced.
        return checkHeightAndBalance(root) != -1;
    }

    /**
     * Helper function that recursively calculates the height of a subtree
     * and simultaneously checks if it's balanced.
     *
     * @param node The current node being processed.
     * @return The height of the subtree rooted at 'node' if it's balanced.
     *         Returns -1 if the subtree is unbalanced at any point.
     */
    private int checkHeightAndBalance(TreeNode node) {
        // Base case: A null node has a height of -1 and is considered balanced.
        if (node == null) {
            return -1;
        }

        // Recursively get the height and balance status of the left subtree.
        int leftHeight = checkHeightAndBalance(node.left);
        // If the left subtree is unbalanced, propagate -1 up immediately.
        if (leftHeight == -1) {
            return -1;
        }

        // Recursively get the height and balance status of the right subtree.
        int rightHeight = checkHeightAndBalance(node.right);
        // If the right subtree is unbalanced, propagate -1 up immediately.
        if (rightHeight == -1) {
            return -1;
        }

        // Check if the current node's subtrees are balanced according to the definition.
        // The absolute difference in heights must not be greater than 1.
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1; // Current node's subtree is unbalanced.
        }

        // If all checks pass, the current subtree is balanced.
        // Its height is 1 (for the current node) + the maximum height of its children.
        return 1 + Math.max(leftHeight, rightHeight);
    }

    // Example Usage (for testing purposes, not part of the main solution)
    public static void main(String[] args) {
        BalancedBinaryTree solver = new BalancedBinaryTree();

        // Balanced tree example
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);
        System.out.println("Tree 1 is balanced: " + solver.isBalanced(root1)); // Expected: true

        // Unbalanced tree example (left skewed)
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.left.left = new TreeNode(3);
        root2.left.left.left = new TreeNode(4);
        System.out.println("Tree 2 is balanced: " + solver.isBalanced(root2)); // Expected: false

        // Unbalanced tree example (right skewed)
        TreeNode root3 = new TreeNode(1);
        root3.right = new TreeNode(2);
        root3.right.right = new TreeNode(3);
        System.out.println("Tree 3 is balanced: " + solver.isBalanced(root3)); // Expected: false

        // Unbalanced tree example (difference > 1 at root)
        TreeNode root4 = new TreeNode(1);
        root4.left = new TreeNode(2);
        root4.left.left = new TreeNode(3);
        root4.right = new TreeNode(4);
        System.out.println("Tree 4 is balanced: " + solver.isBalanced(root4)); // Expected: false
    }
}

Explanation Walkthrough:

Let's walk through our Java solution step-by-step.

1. TreeNode Class: We start with a standard TreeNode class, a common building block for tree problems. It holds an integer val and references to its left and right children.
2. isBalanced(TreeNode root): This is our public entry point.
   • We handle the edge case of an empty tree (root == null) immediately, returning true as an empty tree is by definition balanced.
   • The core logic delegates to our private helper function, checkHeightAndBalance. If this helper returns -1, it signifies that an imbalance was detected somewhere in the tree, so isBalanced returns false. Otherwise, it returns true.
3. checkHeightAndBalance(TreeNode node): This is where the magic happens. This recursive function serves a dual purpose: it calculates the height of the subtree rooted at node and checks if that subtree is balanced.
   • Base Case (node == null): If we encounter a null node, it means we've gone past a leaf. A null subtree has a height of -1 (a common convention where a single node has height 0, and its children are at height -1) and is inherently balanced. We return -1.
   • Recursive Calls:
     • We first recursively call checkHeightAndBalance on the node.left child. The result, leftHeight, will be either the actual height of the left subtree (if balanced) or -1 (if unbalanced).
     • Early Exit (Left Subtree): If leftHeight is -1, we know immediately that the left subtree is unbalanced. Since an unbalanced subtree makes the entire tree unbalanced, we can stop processing and return -1 right away. This is a crucial optimization that prevents unnecessary computations.
     • We then do the same for the node.right child, getting rightHeight.
     • Early Exit (Right Subtree): Similarly, if rightHeight is -1, we return -1.
   • Balance Check at Current Node: If both leftHeight and rightHeight are valid (not -1), it means both subtrees are individually balanced. Now, we need to check if this current node maintains the balance property. We calculate the absolute difference between leftHeight and rightHeight. If Math.abs(leftHeight - rightHeight) > 1, then the current node's subtrees differ too much in height, making the tree unbalanced at this point. We return -1.
   • Return Height: If all checks pass – both subtrees are balanced, and their heights don't differ by more than one – then the subtree rooted at node is balanced. Its height is 1 + Math.max(leftHeight, rightHeight) (1 for the current node itself, plus the height of its taller child). We return this calculated height.

Time & Space Complexity

Let's analyze the efficiency of our solution.

• Each node in the binary tree is visited exactly once by our checkHeightAndBalance recursive function. During each visit, we perform a constant amount of work (checking for null, making two recursive calls, performing an absolute difference calculation, and a max operation).
• Therefore, the total time complexity is directly proportional to the number of nodes, N, making it O(N). This is optimal, as we must at least visit every node to verify the balance property.
• The space complexity is determined by the maximum depth of the recursion stack. In the worst-case scenario, for a skewed tree (like a linked list), the height H can be equal to N (the number of nodes). In this case, the space complexity would be O(N).
• For a perfectly balanced tree, the height H is O(log N), so the space complexity would be O(log N).
• Thus, the space complexity is O(H), where H is the height of the tree.

Space Complexity: O(H)

Time Complexity: O(N)

Why This Problem Matters (The Senior Perspective)

This problem, while seemingly a straightforward tree traversal, is a cornerstone for understanding more advanced data structures and algorithms. From a senior engineer's perspective, here's why it's so important:

1. Foundation for Self-Balancing Trees: The concept of a 'balanced' tree is not just academic. It's the very reason why data structures like AVL Trees and Red-Black Trees exist. These are self-balancing Binary Search Trees (BSTs) that automatically adjust their structure during insertions and deletions to maintain a balanced state. Without balance, a BST degrades into a linked list in the worst case, turning O(log N) operations (search, insert, delete) into O(N). Understanding how to check for balance is the first step to understanding how to maintain it.
2. Optimizing Recursive Solutions: Our solution demonstrates a powerful pattern: combining multiple pieces of information (height and balance status) into a single recursive pass. This avoids redundant computations that a naive approach (calculating height for every node independently) would incur. This 'pass-up' information strategy is invaluable for optimizing many tree and graph algorithms.
3. Real-World Performance: In production systems, if you're using tree-based data structures (e.g., for indexing, caching, or hierarchical data), their performance hinges on their balance. An unbalanced tree can lead to performance bottlenecks, increased latency, and even system instability under heavy load. Being able to identify and, more importantly, prevent such scenarios is a critical skill.
4. Robust Error Handling and Early Exits: The use of a sentinel value (-1) and early exits (if (leftHeight == -1) return -1;) is a practical technique for propagating error conditions or 'failure' states efficiently up the call stack. This prevents unnecessary work once an invalid state is detected, improving both performance and code clarity.
5. Architectural Implications: When designing systems that rely on tree-like structures, you often need to consider how to ensure their efficiency. This problem helps you internalize the trade-offs. Should you use a simple binary tree and accept potential O(N) worst-case performance, or invest in a more complex self-balancing structure for guaranteed O(log N)? The answer often depends on the scale, frequency of operations, and performance requirements of your application.

Final Thoughts

Mastering problems like 'Check Balanced Binary Tree' isn't just about passing an interview; it's about building a deeper intuition for how data structures behave and how to write efficient, robust algorithms. We've seen how a clever recursive strategy can transform a potentially inefficient solution into an optimal one by combining operations and leveraging early exits.

As you continue your journey, I encourage you to think about how you might extend this. How would you modify this to make a tree balanced? What if the definition of 'balanced' changed slightly? These are the kinds of questions that push us from simply solving problems to truly understanding and designing systems.

Keep practicing, keep exploring, and keep learning!