Count Total Nodes in Binary Tree in DSA Javascript - 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) {
  if (root === null) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}
    

This code counts all nodes by visiting each node once using recursion.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call 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: Doubling the nodes roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The recursion might visit some nodes multiple times, so it could be slower than linear."

[OK] Correct: Each node is visited exactly once because the function calls only go down the tree branches without repeats.

Interview Connect

Understanding this linear time complexity helps you explain how recursive tree traversals work efficiently in real problems.

Self-Check

"What if we changed the tree to a linked list (all nodes have only one child)? How would the time complexity change?"