Count Total Nodes in Binary Tree in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree?

A binary tree is a structure where each node has at most two children called left and right child.

beginner

How do you count total nodes in a binary tree?

Count nodes by adding 1 for the current node plus counts of nodes in left and right subtrees recursively.

beginner

What is the base case when counting nodes recursively in a binary tree?

When the node is null (no node), return 0 because there are no nodes to count.

intermediate

Why do we use recursion to count nodes in a binary tree?

Recursion helps visit each node and count it, then combine counts from left and right children easily.

intermediate

What is the time complexity of counting total nodes in a binary tree?

The time complexity is O(n), where n is the number of nodes, because each node is visited once.

What should the count function return when it reaches a null node?

A 0

B 1

C -1

D null

When the node is null, it means no node exists, so the count is 0.

If a binary tree has only one node, what is the total count of nodes?

A 1

B 2

C 0

D Depends on children

A single node tree has exactly one node.

Which traversal method is naturally used when counting nodes recursively?

A Inorder

B Preorder

C Postorder

D Level order

Preorder traversal visits the current node first, then children, which fits counting nodes.

What is the total node count of a binary tree with root and two children?

A 1

B 4

C 2

D 3

Root plus two children equals three nodes total.

What is the main reason recursion is preferred for counting nodes in binary trees?

A It uses less memory

B It uses loops

C It simplifies visiting all nodes

D It avoids visiting nodes

Recursion simplifies visiting each node and combining counts from subtrees.

Explain how to count total nodes in a binary tree using recursion.

Think about visiting each node and adding counts from children.

Describe the time complexity of counting nodes in a binary tree and why.

Consider how many times the function runs for each node.

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