Count Total Nodes in Binary Tree in DSA Typescript

Mental Model

We want to find how many pieces (nodes) are in a tree by visiting each piece once.

Analogy: Imagine counting all the apples on a tree by picking each branch and counting apples on it, then adding them up.

    1
   / \
  2   3
 / 
4  

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has left child 4

Goal: Count all nodes in the tree

Step 1: Start at root node 1, count 1 for this node

1 (count=1)

Why: We count the current node before checking children

Step 2: Move to left child node 2, count 1 for this node

1 -> 2 (count=1 for node 2)

Why: We count left subtree nodes

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

1 -> 2 -> 4 (count=1 for node 4)

Why: We count left subtree of node 2

Step 4: Node 4 has no children, return count 1

4 (leaf node)

Why: Leaf node counts as 1

Step 5: Node 2 has no right child, total count for node 2 subtree is 1 (left) + 0 (right) + 1 (node 2) = 2

2 subtree count = 2

Why: Sum counts of left, right, and current node

Step 6: Move to right child node 3, count 1 for this node

3 (count=1)

Why: Count right subtree nodes

Step 7: Node 3 has no children, return count 1

3 (leaf node)

Why: Leaf node counts as 1

Step 8: Total count for root node 1 is 2 (left subtree) + 1 (right subtree) + 1 (root) = 4

Total nodes = 4

Why: Sum counts of left, right, and root nodes

Result:

1 -> 2 -> 4 -> 3 -> null
Total nodes: 4

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function countNodes(root: TreeNode | null): number {
  if (root === null) return 0; // base case: no node here
  const leftCount = countNodes(root.left); // count nodes in left subtree
  const rightCount = countNodes(root.right); // count nodes in right subtree
  return leftCount + rightCount + 1; // add current node
}

// Driver code to build tree and count nodes
const node4 = new TreeNode(4);
const node2 = new TreeNode(2, node4, null);
const node3 = new TreeNode(3);
const root = new TreeNode(1, node2, node3);

const totalNodes = countNodes(root);
console.log("1 -> 2 -> 4 -> 3 -> null");
console.log("Total nodes:", totalNodes);

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

stop counting when no node exists

const leftCount = countNodes(root.left); // count nodes in left subtree

recursively count nodes in left subtree

const rightCount = countNodes(root.right); // count nodes in right subtree

recursively count nodes in right subtree

return leftCount + rightCount + 1; // add current node

sum counts of left, right, and current node

Output

1 -> 2 -> 4 -> 3 -> null

Total nodes: 4

Complexity Analysis

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

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

vs Alternative: Compared to iterative traversal, recursive counting is simpler but uses call stack; iterative may use explicit stack with similar time

Edge Cases

Empty tree (root is null)

Returns 0 because there are no nodes

DSA Typescript

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

Single node tree

Returns 1 because only root node exists

DSA Typescript

return leftCount + rightCount + 1; // add current node

Tree with only left children

Counts all nodes by recursively going left

DSA Typescript

const leftCount = countNodes(root.left); // count nodes in left subtree

When to Use This Pattern

When asked to find the total number of nodes in a tree, use recursive counting by summing left and right subtree counts plus one for the current node.

Common Mistakes

Mistake: Forgetting to add 1 for the current node in the return statement
Fix: Always add 1 to the sum of left and right subtree counts to include the 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 left subtree, right subtree, then add one for the current node.