Count Total Nodes in Binary Tree in DSA Typescript - Time & Space Complexity

Time Complexity: Count Total Nodes in Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to count all nodes in a binary tree.

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function countNodes(root: TreeNode | null): number {
  if (root === null) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}
    

This code counts all nodes by visiting each node once in the binary tree.

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

Each node is visited 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 count nodes grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Counting nodes is faster because we only check the root or just one side."

[OK] Correct: Every node must be visited to count it, so skipping parts misses nodes and gives wrong results.

Interview Connect

Counting nodes is a basic skill that shows you understand tree traversal and recursion, which are common in many problems.

Self-Check

"What if we used an iterative approach with a stack instead of recursion? How would the time complexity change?"