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

Concept Flow - Count Total Nodes in Binary Tree

Start at root node

↓

Is node None?

Yes→Return 0

No↓

Count left subtree nodes

↓

Count right subtree nodes

↓

Sum left + right + 1 (current node)

↓

Return total count

The process starts at the root, recursively counts nodes in left and right subtrees, then adds 1 for the current node.

Execution Sample

DSA Python

def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(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	A	-	-	-	A / \ B C / D
2	Visit left child	B	-	-	-	A / \ B C / D
3	Visit B's left child	D	-	-	-	A / \ B C / D
4	D is leaf, left None	None	0	-	-	A / \ B C / D
5	D is leaf, right None	None	-	0	-	A / \ B C / D
6	Count D nodes	D	0	0	1	A / \ B C / D
7	Visit B's right child	None	-	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	None	0	-	-	A / \ B C / D
11	Visit C's right child	None	-	0	-	A / \ B C / D
12	Count C nodes	C	0	0	1	A / \ B C / D
13	Count root nodes	A	2	1	4	A / \ B C / D
14	Return total count	-	-	-	4	A / \ B C / D

💡 All nodes visited; total count is 4

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 12	Final
current node	A	D	B	C	A
left count	-	0	1	0	2
right count	-	0	0	0	1
total count	-	1	2	1	4

Key Moments - 3 Insights

Why do we return 0 when the node is None?

Returning 0 at None nodes (leaf children) means no nodes exist there, so they don't add to the count (see Step 4 and 5 in execution_table).

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

The function calls itself recursively on left and right children, sums their counts, then adds 1 for the current node (see Steps 6, 8, 12, and 13).

Why is the total count 4 at the end?

Because the tree has 4 nodes: A, B, C, and D. The function counts each node once during traversal (see Step 14).

Visual Quiz - 3 Questions

Look at the execution_table, what is the total count after visiting node B (Step 8)?

A 1

B 3

C 2

D 4

💡 Hint

Check the 'Total Count' column at Step 8 in execution_table.

At which step does the function return 0 for a None node?

A Step 3

B Step 4

C Step 6

D Step 13

💡 Hint

Look for steps where 'Node Visited' is None and counts are 0 in execution_table.

If node D had a right child, how would the total count at Step 14 change?

A It would increase by 1

B It would stay the same

C It would decrease by 1

D It would double

💡 Hint

Adding a new node increases total count by 1; see how counts add up in execution_table.

Concept Snapshot

Count Total Nodes in Binary Tree:
- Use recursion starting at root
- If node is None, return 0
- Else return 1 + count(left) + count(right)
- Counts all nodes including root
- Total count is sum of all nodes visited

Full Transcript

To count total nodes in a binary tree, start at the root node. If the node is None, return 0 because there are no nodes there. Otherwise, recursively count nodes in the left subtree and right subtree, then add 1 for the current node. This process continues until all nodes are visited. The final count is the total number of nodes in the tree. For example, in a tree with nodes A, B, C, and D, the function visits each node once and sums counts to get 4.

Practice

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

easy

A. 1

B. 0

C. -1

D. None

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 return value for empty tree

   The function should return 0 to indicate no nodes exist.

3. Final Answer:

   0 -> Option B

4. Quick Check:

   Empty tree nodes = 0 [OK]

Hint: Empty tree always has zero nodes [OK]

Common Mistakes:

• Returning 1 for empty tree
• Returning None instead of 0
• Returning -1 as error code

2. Which of the following is the correct Python syntax to define a recursive function named count_nodes that takes a parameter root?

easy

A. count_nodes(root) def:

B. function count_nodes(root):

C. def count_nodes -> root:

D. def count_nodes(root):

Solution

1. Step 1: Recall Python function definition syntax

   In Python, functions are defined using the def keyword followed by the function name and parameters in parentheses.

2. Step 2: Match the correct syntax

   def count_nodes(root): correctly uses def count_nodes(root): which is valid Python syntax.

3. Final Answer:

   def count_nodes(root): -> Option D

4. Quick Check:

   Python functions start with def and parentheses [OK]

Hint: Python functions start with def and parentheses [OK]

Common Mistakes:

• Using 'function' keyword
• Incorrect arrow syntax
• Misplacing def after parameters

3. What is the output of the following code snippet?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
print(count_nodes(root))

medium

A. 4

B. 3

C. 5

D. Error

Solution

1. Step 1: Count nodes in the tree structure

   The tree has nodes: 10 (root), 5 (left), 15 (right), and 3 (left of 5). Total nodes = 4.

2. Step 2: Confirm recursive count

   The function counts 1 for root + counts left subtree (2 nodes) + counts right subtree (1 node) = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Total nodes counted = 4 [OK]

Hint: Add 1 plus counts of left and right subtrees [OK]

Common Mistakes:

• Counting only root and children
• Ignoring left.left node
• Returning error due to None check missing

4. Find the error in the following code that counts total nodes in a binary tree:

def count_nodes(root):
    if root == None:
        return 1
    return 1 + count_nodes(root.left) + count_nodes(root.right)

medium

A. Base case returns 1 instead of 0 for None

B. Missing colon after function definition

C. Using '==' instead of 'is' for None check

D. No return statement in recursive call

Solution

1. Step 1: Analyze base case return value

   The base case should return 0 when the node is None because no node exists there.

2. Step 2: Identify incorrect return value

   Returning 1 for None causes overcounting nodes, leading to wrong total count.

3. Final Answer:

   Base case returns 1 instead of 0 for None -> Option A

4. Quick Check:

   Base case must return 0 for empty node [OK]

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

Common Mistakes:

• Returning 1 for None
• Confusing '==' and 'is' but both work
• Missing colon is syntax error

5. Given a binary tree where each node has either 0 or 2 children, and the total number of leaf nodes is 7, what is the total number of nodes in the tree?

hard

A. 15

B. 14

C. 13

D. 16

Solution

1. Step 1: Use property of full binary tree

   In a full binary tree, total nodes = 2 * leaf nodes - 1.

2. Step 2: Calculate total nodes

   Total nodes = 2 * 7 - 1 = 14 - 1 = 13.

3. Step 3: Recheck formula correctness

   Actually, total nodes = 2 * leaf nodes - 1 = 13, but the options include 15 which is the total nodes for a perfect binary tree of height 3 (which has 7 leaves and 15 nodes). Since the tree has nodes with either 0 or 2 children (full binary tree), the formula applies and the correct total nodes is 13.

4. Final Answer:

   13 -> Option C

5. Quick Check:

   Total nodes = 2 * leaves - 1 = 13 [OK]

Hint: Full binary tree nodes = 2 * leaves - 1 [OK]

Common Mistakes:

• Using total nodes = leaves * 2
• Confusing full and complete tree formulas
• Ignoring leaf node count