Balanced Binary Tree

Problem Statement

In the realm of binary trees, a tree is considered height-balanced if, for every node in the tree, the difference in heights between its left and right subtrees is no more than 1. The problem at hand involves taking a binary tree and determining whether it conforms to this height-balance condition.

Examples

Example 1

Input:

root = [3,9,20,null,null,15,7]

Output:

true

Example 2

Input:

root = [1,2,2,3,3,null,null,4,4]

Output:

false

Example 3

Input:

root = []

Output:

true

Constraints

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

Approach and Intuition

Let's dissect how to approach the given problem using the examples provided:

1. By definition, for the binary tree to be height-balanced, each node within the tree must have its left and right subtree heights differing by at most 1.

Intuitive Explanation Using Provided Examples

• Example 1: [3,9,20,null,null,15,7]
  • Here, the binary tree's root node is 3, with subtrees 9 (left) and 20 (right).
  • Node 9 is a leaf without further children, thus balanced.
  • Node 20 has further subtrees consisting of 15 and 7, both of which are leaves and thus balanced.
  • The entire tree maintains a balanced condition due to each node satisfying the height balance criterion.
• Example 2: [1,2,2,3,3,null,null,4,4]
  • The root node 1 has subtrees at nodes 2.
  • Each node 2 again branches out into nodes 3. However, the nodes 3 further branch into nodes 4, causing excessive depth on one side.
  • Here, the subtrees at node 3 result in an imbalance since one path (ending in node 4) is deeper than another (without additional nodes).
  • Thus, this tree fails the height-balance condition for some nodes.
• Example 3: []
  • This is an edge case where the tree is empty.
  • An empty tree is trivially balanced since there are no nodes to cause imbalance.

Constraints Review

• The trees to be examined contain between 0 and 5000 nodes.
• Each node’s value ranges from -10,000 to 10,000, but note that the values do not influence the balance condition, which focuses solely on the structure.

From this understanding, the solution involves constructing a recursive method that:

• Checks the height of left and right subtrees of each node.
• Ensures the height difference is no more than 1 while also confirming that both subtrees themselves are balanced.

Solutions

class Solution {
private:
    // Determines if a binary tree is height-balanced and records the height
    bool checkBalance(TreeNode* node, int& height) {
        if (!node) {
            height = -1;
            return true;
        }
    
        int leftHeight, rightHeight;
        if (checkBalance(node->left, leftHeight) && checkBalance(node->right, rightHeight) && abs(leftHeight - rightHeight) < 2) {
            height = 1 + max(leftHeight, rightHeight);
            return true;
        }
        return false;
    }
    
public:
    bool isBalanced(TreeNode* root) {
        int treeHeight;
        return checkBalance(root, treeHeight);
    }
};