Count Total Nodes in Binary Tree in DSA Javascript - 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

↓

Add 1 (current node) + left count + right count

↓

Return total count

The process starts at the root, checks if the node is null, then recursively counts nodes in left and right subtrees, adding 1 for the current node.

Execution Sample

DSA Javascript

function countNodes(node) {
  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 from left and right children plus the current node.

Execution Table

Step	Operation	Node Visited	Left Count	Right Count	Total Count	Tree State
1	Visit root	A	-	-	-	A / \ B C
2	Visit left child	B	-	-	-	A / \ B C
3	Visit B's left child	D	-	-	-	A / \ B C / D
4	D is leaf, left null	null	0	-	-	A / \ B C / D
5	D is leaf, right null	null	-	0	-	A / \ B C / D
6	Count D nodes	D	0	0	1	A / \ B C / D
7	Visit B's right child	null	0	-	-	A / \ B C / D
8	Count B nodes	B	1	0	2	A / \ B C / D
9	Visit right child	C	-	-	-	A / \ B C / D
10	Visit C's left child	null	0	-	-	A / \ B C / D
11	Visit C's right child	E	-	-	-	A / \ B C / D \ E
12	E is leaf, left null	null	0	-	-	A / \ B C / D \ E
13	E is leaf, right null	null	-	0	-	A / \ B C / D \ E
14	Count E nodes	E	0	0	1	A / \ B C / D \ E
15	Count C nodes	C	0	1	2	A / \ B C / D \ E
16	Count root nodes	A	2	2	5	A / \ B C / D \ E
17	Return total count	A	2	2	5	Final count: 5 nodes

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

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 14	After Step 15	After Step 16	Final
node	A (root)	D (leaf)	B (left child)	E (leaf)	C (right child)	A (root)	null (end)
leftCount	-	0	1	0	0	2	2
rightCount	-	0	0	0	1	2	2
totalCount	-	1	2	1	2	5	5

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 at null nodes (see Step 4 and 5) stops recursion and counts no nodes beyond leaves.

How does the function add counts from left and right subtrees?

At each node (e.g., Step 16), it adds 1 (current node) plus leftCount and rightCount from recursive calls.

Why does the total count at root equal 5?

Because it sums all nodes counted in left subtree (2), right subtree (2), plus 1 for root itself (Step 16).

Visual Quiz - 3 Questions

Look at the execution table, what is the totalCount at Step 8?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'totalCount' column at Step 8 in the execution_table.

At which step does the function visit node E?

A Step 14

B Step 10

C Step 11

D Step 15

💡 Hint

Look for 'Visit C's right child' operation in the execution_table.

If node D had a left child, how would the totalCount at Step 6 change?

A It would increase

B It would decrease

C It would remain 1

D It would become 0

💡 Hint

Adding a child node increases the count returned at that subtree (see how counts add in execution_table).

Concept Snapshot

Count Total Nodes in Binary Tree:
- Use recursion starting at root
- If node is null, return 0
- Else return 1 + count(left) + count(right)
- Counts all nodes including root
- Stops at leaves with null children

Full Transcript

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