Count Total Nodes in Binary Tree in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to count nodes by returning 1 plus counts of left and right subtrees.

DSA Python

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

Drag options to blanks, or click blank then click option'

Achild

Bright

Cleft

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using root.right twice instead of root.left and root.right.

Using a wrong attribute name like root.child.

We count the current node (1) plus nodes in the left subtree (root.left) and right subtree (root.right).

2fill in blank

medium

Complete the code to check if the tree is empty by comparing root to {{BLANK_1}}.

DSA Python

def count_nodes(root):
    if root == [1]:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

Drag options to blanks, or click blank then click option'

ANone

B0

CFalse

D''

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or False instead of None to check for empty tree.

Using empty string '' which is incorrect.

We check if root is None to know if the tree or subtree is empty.

3fill in blank

hard

Fix the error in the recursive call to count nodes in the right subtree.

DSA Python

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

Drag options to blanks, or click blank then click option'

Aright

Bleftt

Crigt

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Misspelling 'right' as 'rigt' or 'leftt'.

Using an invalid attribute like 'node'.

The correct attribute for the right child is root.right.

4fill in blank

hard

Fill both blanks to complete the dictionary comprehension that maps each node's value to its subtree size if the value is greater than 10.

DSA Python

sizes = {node.val: count_nodes(node) for node in nodes if node.val [1] 10 and node.[2] is not None}

Drag options to blanks, or click blank then click option'

A>

B<

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' for value comparison.

Checking right child instead of left child.

We want nodes with value greater than 10 and check if left child exists (node.left is not None).

5fill in blank

hard

Fill both blanks to create a dictionary mapping uppercase node values to their counts if count is greater than 1.

DSA Python

result = {node.val[1]: count for node, count in counts.items() if count [2] 1 and node.val is not None}

Drag options to blanks, or click blank then click option'

A.upper()

B>

D.lower()

Attempts:

3 left

💡 Hint

Common Mistakes

Using .lower() instead of .upper().

Using '<' instead of '>' for count comparison.

Adding unwanted characters after node.val.

We convert node.val to uppercase with .upper(), check count > 1, and ensure node.val is not None (empty string means no change).

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