Balanced Binary Tree

Balanced Binary Tree

What is this problem about?

The Balanced Binary Tree interview question asks you to determine if a given binary tree is "height-balanced." A binary tree is height-balanced if, for every node, the height of its left and right subtrees differs by no more than one. This Balanced Binary Tree coding problem is a core tree recursion task.

Why is this asked in interviews?

Amazon, Apple, and Microsoft use this to test your ability to perform post-order traversals and calculate properties from the bottom up. It evaluates whether you can optimize the search by "pruning"—returning early once an imbalance is detected.

Algorithmic pattern used

This follows the Depth-First Search, Binary Tree, Tree interview pattern. You write a recursive function that returns the height of a node. If an imbalance is found at any sub-node, the function returns a special value (like -1) to signal the failure all the way up the stack.

Example explanation

      3
     / 
    9  20
      /  
     15   7

1. Check Node 15: H=1. Check Node 7: H=1. |1-1| = 0 <= 1. Node 20 height = 2.
2. Check Node 9: H=1.
3. Check Node 3: Left H=1, Right H=2. |1-2| = 1 <= 1. Result: Balanced. If 15 had a child, Node 20 would have H=3, and Node 3 would see |1-3|=2, making it unbalanced.

Common mistakes candidates make

• Redundant Calculations: Calling a separate height() function for every node, leading to O(N^2) complexity. The height and balance check should be done in a single O(N) pass.
• Null Handling: Not correctly defining the height of a null node (usually 0).
• Early Return: Forgetting to stop the recursion once a -1 (unbalanced) is detected in a subtree.

Interview preparation tip

Whenever you need to check a property that depends on the heights of subtrees, think about returning the height while checking the property. This prevents re-traversing the same nodes multiple times.