Check if Binary Tree is Balanced in DSA C++ - Time & Space Complexity

Time Complexity: Check if Binary Tree is Balanced

O(n²)

Understanding Time Complexity

We want to know how long it takes to check if a binary tree is balanced.

Specifically, how the time grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int height(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return 1 + std::max(leftHeight, rightHeight);
}

bool isBalanced(TreeNode* root) {
    if (!root) return true;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (abs(leftHeight - rightHeight) > 1) return false;
    return isBalanced(root->left) && isBalanced(root->right);
}
    

This code checks if a binary tree is balanced by comparing heights of subtrees recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The height function is called repeatedly for each node.
• How many times: For each node, height is called again on its children, causing repeated calculations.

How Execution Grows With Input

As the tree size grows, the number of height calculations grows quickly because each node's height is recalculated many times.

Input Size (n)	Approx. Operations
10	About 100 calls
100	About 10,000 calls
1000	About 1,000,000 calls

Pattern observation: The operations grow roughly with the square of the number of nodes.

Final Time Complexity

Time Complexity: O(n²)

This means the time to check balance grows very fast as the tree gets bigger, roughly like the number of nodes squared.

Common Mistake

[X] Wrong: "The height function is called only once per node, so the time is O(n)."

[OK] Correct: Actually, height is called many times for the same nodes during recursion, causing repeated work and increasing time.

Interview Connect

Understanding this helps you explain why naive recursion can be slow and how to improve it, a key skill in interviews.

Self-Check

"What if we modified the code to calculate height and balance in the same recursion? How would the time complexity change?"