Count Total Nodes in Binary Tree in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Count nodes in a simple binary tree

What is the output of the following code that counts total nodes in a binary tree?

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
    return 1 + count_nodes(root.left) + count_nodes(root.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(count_nodes(root))

A 3

B 4

C 5

D 6

💡 Hint

Count each node including root, left subtree, and right subtree.

The tree has nodes 1, 2, 3, 4, and 5. Total nodes = 5.

❓ Predict Output

intermediate

Count nodes in a skewed binary tree

What is the output of this code counting nodes in a skewed binary tree?

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
    return 1 + count_nodes(root.left) + count_nodes(root.right)

root = Node(10)
root.right = Node(20)
root.right.right = Node(30)
root.right.right.right = Node(40)

print(count_nodes(root))

A 2

B 4

C 5

D 3

💡 Hint

Count all nodes along the right side.

Nodes are 10, 20, 30, 40. Total nodes = 4.

🧠 Conceptual

advanced

Understanding node count in a full binary tree

If a full binary tree has height 3 (root at height 1), how many total nodes does it have?

A 7

B 8

C 6

D 15

💡 Hint

Full binary tree nodes = 2^height - 1

For height 3, nodes = 2^3 - 1 = 7.

🔧 Debug

advanced

Find the error in counting nodes code

What error does this code produce when counting nodes in a binary tree?

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
    return 1 + count_nodes(root.left) + count_nodes(root.left)

root = Node(1)
root.left = Node(2)
root.right = Node(3)

print(count_nodes(root))

A SyntaxError due to missing colon

B Correct output: 3

C TypeError because root.left is None

D Counts only left subtree nodes twice, missing right subtree nodes

💡 Hint

Check recursive calls carefully.

The code calls count_nodes(root.left) twice, ignoring right subtree.

🚀 Application

expert

Count nodes in a binary tree using iterative approach

Which option correctly counts total nodes in a binary tree using iteration (no recursion)?

DSA Python

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

A

def count_nodes(root):
    if not root:
        return 0
    count = 0
    stack = [root]
    while stack:
        node = stack.pop()
        count += 1
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return count

print(count_nodes(root))

B

def count_nodes(root):
    count = 0
    queue = []
    queue.append(root)
    while queue:
        node = queue.pop(0)
        count += 1
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return count

print(count_nodes(root))

C

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

print(count_nodes(root))

D

def count_nodes(root):
    count = 0
    stack = []
    stack.append(root)
    while stack:
        node = stack.pop()
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return count

print(count_nodes(root))

💡 Hint

Use a stack and increment count for each visited node.

Option A uses a stack and increments count for each node visited. Option A uses pop() on list as queue but should use pop(0) to dequeue from front. Option A is recursive, not iterative. Option A never increments count, so returns 0.

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