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.

Practice

1. What does the function to count total nodes in a binary tree return when the tree is empty?

easy

A. -1

B. 1

C. 0

D. null

Solution

1. Step 1: Understand the base case for an empty tree

   When the binary tree is empty, there are no nodes to count, so the count should be zero.

2. Step 2: Confirm the function's return value for empty input

   The function should return 0 to indicate no nodes exist in the tree.

3. Final Answer:

   0 -> Option C

4. Quick Check:

   Empty tree node count = 0 [OK]

Hint: Empty tree always has zero nodes [OK]

Common Mistakes:

• Returning 1 for empty tree
• Returning null instead of 0
• Confusing empty tree with leaf node

2. Which of the following TypeScript function signatures correctly defines a function to count total nodes in a binary tree node structure?

easy

A. function countNodes(root: number): number

B. function countNodes(root: any): string

C. function countNodes(root: TreeNode): void

D. function countNodes(root: TreeNode | null): number

Solution

1. Step 1: Identify correct parameter type for binary tree root

   The root should be a TreeNode or null if the tree is empty.

2. Step 2: Confirm return type for count function

   The function returns a number representing total nodes, so return type must be number.

3. Final Answer:

   function countNodes(root: TreeNode | null): number -> Option D

4. Quick Check:

   Correct parameter and return types = function countNodes(root: TreeNode | null): number [OK]

Hint: Function must accept node or null and return number [OK]

Common Mistakes:

• Using wrong parameter type
• Returning void instead of number
• Returning string instead of number

3. Given the following binary tree code, what is the output of console.log(countNodes(root));?

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

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

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

medium

A. 5

B. 6

C. 4

D. 3

Solution

1. Step 1: Count nodes in the tree structure

   The tree has nodes: 1 (root), 2 and 3 (children), 4 and 5 (children of 2). Total nodes = 5.

2. Step 2: Verify recursive count function output

   The function counts 1 for root plus counts of left and right subtrees, summing to 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Total nodes counted = 5 [OK]

Hint: Count all nodes including root and children [OK]

Common Mistakes:

• Counting only leaf nodes
• Missing one subtree
• Off-by-one error in count

4. Identify the error in the following TypeScript function to count total nodes in a binary tree:

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

medium

A. Function does not count the current node

B. Base case returns 1 instead of 0 for null

C. Missing return type annotation

D. Incorrect parameter type

Solution

1. Step 1: Check base case return value

   The base case returns 1 when root is null, which incorrectly counts non-existent nodes.

2. Step 2: Understand correct base case for counting nodes

   For null nodes, the count should be 0, not 1, to avoid overcounting.

3. Final Answer:

   Base case returns 1 instead of 0 for null -> Option B

4. Quick Check:

   Base case must return 0 for null [OK]

Hint: Base case for null must return 0 nodes [OK]

Common Mistakes:

• Returning 1 for null node
• Not counting current node
• Wrong parameter or return types

5. You want to count total nodes in a binary tree but only count nodes with even values. Which modification to the standard count function is correct?

function countEvenNodes(root: TreeNode | null): number {
  if (!root) return 0;
  const leftCount = countEvenNodes(root.left);
  const rightCount = countEvenNodes(root.right);
  // What to add here?
}

hard

A. return (root.val % 2 === 0 ? 1 : 0) + leftCount + rightCount;

B. return 1 + leftCount + rightCount;

C. return leftCount + rightCount;

D. return (root.val % 2 !== 0 ? 1 : 0) + leftCount + rightCount;

Solution

1. Step 1: Check node value for evenness

   Use modulo operator to check if root.val is even; if yes, count 1, else 0.

2. Step 2: Sum counts from left, right, and current node if even

   Add leftCount, rightCount, and 1 or 0 based on current node's evenness.

3. Final Answer:

   return (root.val % 2 === 0 ? 1 : 0) + leftCount + rightCount; -> Option A

4. Quick Check:

   Count only even nodes correctly [OK]

Hint: Add 1 only if node value is even [OK]

Common Mistakes:

• Counting all nodes regardless of value
• Counting odd nodes instead
• Forgetting to add left and right counts