Count Total Nodes in Binary Tree in DSA Go - 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 + right

↓

Return total count

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

Execution Sample

DSA Go

func countNodes(root *Node) int {
    if root == nil {
        return 0
    }
    return 1 + countNodes(root.Left) + countNodes(root.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 Count	Right Count	Total Count	Tree State
1	Visit root	1	-	-	-	1 / \ 2 3
2	Visit left child	2	-	-	-	1 / \ 2 3
3	Visit left.left (nil)	nil	0	0	0	1 / \ 2 3
4	Visit left.right (nil)	nil	0	0	0	1 / \ 2 3
5	Count left subtree of node 2	2	0	0	1	1 / \ 2 3
6	Visit right child	3	-	-	-	1 / \ 2 3
7	Visit right.left (nil)	nil	0	0	0	1 / \ 2 3
8	Visit right.right (nil)	nil	0	0	0	1 / \ 2 3
9	Count right subtree of node 3	3	0	0	1	1 / \ 2 3
10	Count total nodes at root	1	1	1	3	1 / \ 2 3
11	Return total count	root	-	-	3	1 / \ 2 3

💡 All nodes visited; recursion ends when nil nodes are reached returning 0.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	Final
Current Node	1 (root)	2 (left child)	2 (left child)	3 (right child)	1 (root)
Left Count	-	-	0	0	1
Right Count	-	-	-	0	1
Total Count	-	-	1	1	3

Key Moments - 3 Insights

Why do we return 0 when the node is nil?

Because a nil node means no node exists there, so it contributes zero to the count. This is shown in steps 3, 4, 7, and 8 where nil nodes return 0.

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

The function recursively calls itself on left and right children, sums their counts, and adds 1 for the current node. This is clear in steps 5, 9, and 10.

Why do we add 1 in the return statement?

The 1 accounts for the current node itself. Without it, only children would be counted. Step 10 shows adding 1 + left + right counts.

Visual Quiz - 3 Questions

Look at the execution table, what is the total count returned at step 10?

A 1

B 2

C 3

D 0

💡 Hint

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

At which step does the function visit the right child of the root?

A Step 2

B Step 6

C Step 9

D Step 5

💡 Hint

Look at the 'Operation' and 'Node Visited' columns to find when node 3 is visited.

If the left child of the root had one child node, how would the total count at step 10 change?

A It would increase by 1

B It would decrease by 1

C It would stay the same

D It would double

💡 Hint

Adding a node increases total count by 1; check how counts are summed in steps 5 and 10.

Concept Snapshot

CountTotalNodes(root):
- If root is nil, return 0
- Else return 1 + CountTotalNodes(root.Left) + CountTotalNodes(root.Right)
- Recursively counts all nodes in left and right subtrees
- Adds 1 for current node
- Returns total nodes in tree

Full Transcript

This visualization shows how to count total nodes in a binary tree using recursion. Starting at the root, the function checks if the node is nil. If yes, it returns 0. Otherwise, it recursively counts nodes in the left subtree, then the right subtree, adds 1 for the current node, and returns the sum. The execution table traces each step visiting nodes 1, 2, and 3, including nil children returning 0. The variable tracker shows how counts accumulate. Key moments clarify why nil nodes return 0, why 1 is added for the current node, and how left and right counts combine. The quiz tests understanding of counts at specific steps and effects of adding nodes.