Height of Binary Tree in DSA Typescript - Time & Space Complexity

Time Complexity: Height of Binary Tree

O(n)

Understanding Time Complexity

We want to know how long it takes to find the height of a binary tree as the tree grows bigger.

The question is: how does the time needed change when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function heightOfBinaryTree(root: TreeNode | null): number {
  if (root === null) return 0;
  const leftHeight = heightOfBinaryTree(root.left);
  const rightHeight = heightOfBinaryTree(root.right);
  return Math.max(leftHeight, rightHeight) + 1;
}
    

This code finds the height by checking the height of left and right subtrees recursively and returning the larger one plus one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Each node in the tree is visited exactly one time.

How Execution Grows With Input

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

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

Pattern observation: The time grows linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the height grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The height calculation only depends on the longest path, so it should be faster than visiting all nodes."

[OK] Correct: Even though height depends on the longest path, the function must check every node to be sure no taller path exists, so it visits all nodes.

Interview Connect

Understanding this helps you explain how recursive tree algorithms work and how their time depends on tree size, a common topic in interviews.

Self-Check

"What if the tree was balanced versus very skewed? How would the time complexity change?"