Check if Binary Tree is Balanced in DSA Typescript - 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: TreeNode | null): boolean {
  function height(node: TreeNode | null): number {
    if (!node) return 0;
    const leftHeight = height(node.left);
    if (leftHeight === -1) return -1;
    const rightHeight = height(node.right);
    if (rightHeight === -1) return -1;
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;
    return Math.max(leftHeight, rightHeight) + 1;
  }
  return height(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 to visit 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.

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

Pattern observation: The work grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to check balance grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The function checks balance in O(n log n) time because it calculates height separately for each node."

[OK] Correct: This code calculates height once per node using a single recursion, avoiding repeated height calculations, so it runs in O(n) time.

Interview Connect

Understanding this time complexity helps you explain efficient tree checks clearly and confidently in interviews.

Self-Check

"What if the code calculated height separately for left and right subtrees without early stopping? How would the time complexity change?"