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

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if abs(leftHeight - rightHeight) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    left := height(node.Left)
    right := height(node.Right)
    if left > right {
        return left + 1
    }
    return right + 1
}
    

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: Recursive calls to height inside isBalanced.
• How many times: For each node, height is called multiple times, causing repeated subtree height calculations.

How Execution Grows With Input

As the tree size grows, the number of recursive calls grows quickly because 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 proportional to the square of the number of nodes.

Common Mistake

[X] Wrong: "The function runs in linear time because it visits each node once."

[OK] Correct: The height function is called repeatedly for the same nodes, causing many extra visits and making the total work much larger.

Interview Connect

Understanding this helps you explain why some recursive solutions can be inefficient and how to improve them, a key skill in interviews.

Self-Check

"What if we modified the code to calculate height and balance in a single recursive pass? How would the time complexity change?"