Count Total Nodes in Binary Tree in DSA Javascript

Mental Model

We want to find how many boxes (nodes) are in a tree by visiting each one exactly once.

Analogy: Imagine counting all the rooms in a house by walking through every hallway and door until you have seen every room.

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Binary tree: 1 as root, 2 and 3 as children of 1, 4 and 5 as children of 2

Goal: Count all nodes in the tree

Step 1: Start at root node 1, count 1

Count so far: 1 (node 1)

Why: We begin counting from the root node

Step 2: Move to left child node 2, count 1 more

Count so far: 2 (nodes 1, 2)

Why: We count the left child of root

Step 3: Move to left child of 2, node 4, count 1 more

Count so far: 3 (nodes 1, 2, 4)

Why: We count left subtree nodes

Step 4: Node 4 has no children, backtrack to node 2

Count so far: 3 (nodes 1, 2, 4)

Why: No more nodes down this path

Step 5: Move to right child of 2, node 5, count 1 more

Count so far: 4 (nodes 1, 2, 4, 5)

Why: Count right subtree nodes

Step 6: Node 5 has no children, backtrack to root node 1

Count so far: 4 (nodes 1, 2, 4, 5)

Why: Finished left subtree

Step 7: Move to right child of root, node 3, count 1 more

Count so far: 5 (nodes 1, 2, 4, 5, 3)

Why: Count right subtree node

Step 8: Node 3 has no children, counting complete

Count so far: 5 (all nodes counted)

Why: No more nodes to visit

Result:

Final count: 5 nodes

Annotated Code

DSA Javascript

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

function countNodes(root) {
  if (root === null) return 0; // base case: no node here
  // count current node plus left subtree plus right subtree
  return 1 + countNodes(root.left) + countNodes(root.right);
}

// Build the tree from dry run example
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

const totalNodes = countNodes(root);
console.log(totalNodes);

if (root === null) return 0; // base case: no node here

stop counting when no node exists (leaf child)

return 1 + countNodes(root.left) + countNodes(root.right);

count current node plus all nodes in left and right subtrees

Output

5

Complexity Analysis

Time: O(n) because we visit each node exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Iterative methods with stack or queue also take O(n) time but may use more space

Edge Cases

Empty tree (root is null)

Returns 0 because there are no nodes

DSA Javascript

if (root === null) return 0; // base case: no node here

Single node tree

Returns 1 because only root exists

DSA Javascript

return 1 + countNodes(root.left) + countNodes(root.right);

When to Use This Pattern

When you need to find the total number of elements in a tree, use a recursive count pattern that sums counts from left and right children plus one for the current node.

Common Mistakes

Mistake: Forgetting to return 0 for null nodes causing errors or infinite recursion
Fix: Add base case: if (root === null) return 0;

Mistake: Counting only left or right subtree and missing nodes
Fix: Sum counts from both left and right subtrees plus current node

Summary

Counts all nodes in a binary tree by visiting each node once.

Use when you need the total number of nodes in any binary tree.

The key is to count current node plus counts from left and right subtrees recursively.