Height of Binary Tree in DSA Javascript - 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.

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 height(node) {
  if (node === null) return 0;
  const leftHeight = height(node.left);
  const rightHeight = height(node.right);
  return 1 + Math.max(leftHeight, rightHeight);
}
    

This code finds the height of a binary tree by checking the height of left and right subtrees recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

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 calls
100	About 100 calls
1000	About 1000 calls

Pattern observation: The time grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the height grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The height function only checks one path, so it runs in constant time."

[OK] Correct: The function must visit every node to find the height, not just one path, so it takes time proportional to all nodes.

Interview Connect

Understanding how recursive tree functions scale helps you explain your solutions clearly and shows you know how to handle common data structures.

Self-Check

"What if the tree was balanced vs very unbalanced? How would that affect the time complexity?"