Count Total Nodes in Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Count Total Nodes in Binary Tree

Start at root node

↓

Is node null?

Yes→Return 0

No↓

Count left subtree nodes

↓

Count right subtree nodes

↓

Sum left + right + 1 (current node)

↓

Return total count

The process visits each node starting from the root, counts nodes in left and right subtrees recursively, then sums them with the current node.

Execution Sample

DSA Typescript

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

This function counts all nodes in a binary tree by recursively summing nodes in left and right subtrees plus the current node.

Execution Table

Step	Operation	Node Visited	Left Subtree Count	Right Subtree Count	Total Count	Visual State
1	Start at root	1	-	-	-	1 / \ 2 3
2	Go left	2	-	-	-	1 / 2
3	Go left	4	-	-	-	4 (leaf)
4	Left null	null	0	-	-	null
5	Right null	null	-	0	-	null
6	Count node 4	4	0	0	1	4 (leaf) counted
7	Back to 2, go right	5	-	-	-	5 (leaf)
8	Left null	null	0	-	-	null
9	Right null	null	-	0	-	null
10	Count node 5	5	0	0	1	5 (leaf) counted
11	Count node 2	2	1	1	3	2 subtree counted
12	Back to root, go right	3	-	-	-	3 (leaf)
13	Left null	null	0	-	-	null
14	Right null	null	-	0	-	null
15	Count node 3	3	0	0	1	3 (leaf) counted
16	Count root node 1	1	3	1	5	Full tree counted
17	End	-	-	-	-	Total nodes = 5

💡 All nodes visited; recursion ends when null nodes are reached.

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16	Final
node	1 (root)	4 (leaf)	5 (leaf)	2 (subtree root)	3 (leaf)	1 (root)	null (end)
left subtree count	-	0	0	1	0	3	3
right subtree count	-	0	0	1	0	1	1
total count	-	1	1	3	1	5	5

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 at null nodes (see steps 4,5,8,9,13,14) means no nodes exist there, so they don't add to the count.

How does the function count nodes in left and right subtrees separately?

The function calls itself recursively on node.left and node.right (steps 2,3 for left; steps 12,13 for right), counting nodes in each subtree before summing.

Why do we add 1 after counting left and right subtrees?

Adding 1 (step 16) accounts for the current node itself, ensuring it is included in the total count.

Visual Quiz - 3 Questions

Look at the execution table, what is the total count after counting node 2 (step 11)?

A 1

B 5

C 3

D 0

💡 Hint

Check the 'Total Count' column at step 11 in the execution_table.

At which step does the function return 0 for a null node on the right subtree of node 3?

A Step 13

B Step 14

C Step 15

D Step 16

💡 Hint

Look for 'Right null' operation on node 3 in the execution_table.

If the tree had no right child for the root, how would the total count at step 16 change?

A It would be 4

B It would be 5

C It would be 3

D It would be 1

💡 Hint

Consider the right subtree count column and how missing right child affects total count.

Concept Snapshot

Count Total Nodes in Binary Tree:
- Use recursion starting at root
- If node is null, return 0
- Count nodes in left subtree
- Count nodes in right subtree
- Return sum of left + right + 1 (current node)
- Visits all nodes exactly once

Full Transcript

To count total nodes in a binary tree, start at the root node. If the node is null, return 0 because there are no nodes to count. Otherwise, recursively count nodes in the left subtree and right subtree. Add these counts together and add 1 for the current node. This process repeats until all nodes are visited. The final sum is the total number of nodes in the tree.

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