Count Total Nodes in Binary Tree in DSA Python

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 checking every branch and every apple one by one.

    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

Counting node 1

Why: We must count the root node first

Step 2: Move to left child node 2, count 1 for this node

Counting node 2

Why: We count all nodes, so we visit left child

Step 3: Move to left child of 2, node 4, count 1 for this node

Counting node 4

Why: Continue visiting left subtree

Step 4: Node 4 has no children, return count 1

Return from node 4 with count 1

Why: Leaf node count is 1

Step 5: Node 2 has no right child, return count 1 (node 2) + 1 (node 4) = 2

Return from node 2 with count 2

Why: Sum counts of left and right children plus current node

Step 6: Move to right child of root, node 3, count 1 for this node

Counting node 3

Why: Visit right subtree

Step 7: Node 3 has no children, return count 1

Return from node 3 with count 1

Why: Leaf node count is 1

Step 8: Return total count: 1 (root) + 2 (left subtree) + 1 (right subtree) = 4

Total nodes counted: 4

Why: Sum counts from root and both subtrees

Result:

1 -> 2 -> 4 -> null (left subtree), 3 -> null (right subtree), total nodes = 4

Annotated Code

DSA Python

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
    left_count = count_nodes(root.left)  # count nodes in left subtree
    right_count = count_nodes(root.right)  # count nodes in right subtree
    return 1 + left_count + right_count  # current node + left + right

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

print(count_nodes(root))

if root is None: return 0

base case: no node means count 0

left_count = count_nodes(root.left)

count nodes in left subtree recursively

right_count = count_nodes(root.right)

count nodes in right subtree recursively

return 1 + left_count + right_count

sum current node plus left and right subtree counts

Output

4

Complexity Analysis

Time: O(n) because we visit each of the n nodes exactly once

Space: O(h) where h is the height of the tree due to recursion stack

vs Alternative: This is optimal compared to iterative methods that also visit all nodes; no extra overhead

Edge Cases

Empty tree (root is None)

Returns 0 because there are no nodes

DSA Python

if root is None:
    return 0

Single node tree

Returns 1 because only root exists

DSA Python

return 1 + left_count + right_count

Tree with only left children

Counts all nodes correctly by recursive calls down left

DSA Python

left_count = count_nodes(root.left)

When to Use This Pattern

When asked to find the total number of nodes in a tree, use a recursive count pattern that sums counts from left and right children 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

Mistake: Not handling the base case when root is None
Fix: Add a base case that returns 0 when the node is None to stop recursion

Summary

Counts all nodes in a binary tree by visiting each node once.

Use when you need to know how many nodes are in a tree structure.

The key is to count current node plus counts from left and right subtrees recursively.

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