Check if Binary Tree is Balanced in DSA Javascript - 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.

function isBalanced(root) {
  function checkHeight(node) {
    if (!node) return 0;
    const leftHeight = checkHeight(node.left);
    if (leftHeight === -1) return -1;
    const rightHeight = checkHeight(node.right);
    if (rightHeight === -1) return -1;
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    return Math.max(leftHeight, rightHeight) + 1;
  }
  return checkHeight(root) !== -1;
}
    

This code checks if a binary tree is balanced by measuring heights and stopping early if imbalance is found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Each node is visited once to calculate height and check balance.

How Execution Grows With Input

As the tree grows, the function visits each node once, so operations grow directly with number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: Operations increase linearly as tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to check balance grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The function only checks the root, so it runs in constant time O(1)."

[OK] Correct: The function must visit every node to check heights and balance, so it depends on tree size.

Interview Connect

Understanding this helps you explain how recursion explores trees efficiently and why early stopping matters.

Self-Check

"What if the function did not stop early on imbalance and always checked all nodes? How would the time complexity change?"