Count Total Nodes in Binary Tree in DSA Python - Build from Scratch

Count Total Nodes in Binary Tree

📖 Scenario: You are working with a simple binary tree structure used in many applications like organizing data or decision making. You want to find out how many nodes are in the tree.

🎯 Goal: Build a program that creates a binary tree, then counts and prints the total number of nodes in it.

📋 What You'll Learn

Create a class called Node to represent each node in the binary tree with data, left, and right attributes.

Create a binary tree with exactly 5 nodes using the Node class.

Write a function called count_nodes that takes the root node and returns the total number of nodes in the tree.

Print the total number of nodes in the binary tree.

💡 Why This Matters

🌍 Real World

Binary trees are used in many areas like organizing data, searching quickly, and decision making in games or apps.

💼 Career

Understanding binary trees and recursion is essential for software development roles, especially those involving data structures, algorithms, and system design.

1

Create the Node class and build the binary tree

Create a class called Node with an __init__ method that takes data and sets left and right to None. Then create the binary tree with root node root having value 1, its left child with value 2, right child with value 3, left child of node 2 with value 4, and right child of node 2 with value 5.

DSA Python

# Define the Node class and create the binary tree with 5 nodes
# Your code here

Hint

Think of each node as a box holding a number and two empty spots for left and right children.

2

Create a function to count nodes

Define a function called count_nodes that takes a parameter node. If node is None, return 0. Otherwise, return 1 + count_nodes(node.left) + count_nodes(node.right) to count the current node plus nodes in left and right subtrees.

DSA Python

def count_nodes(node):
    # Your code here

Hint

Count the current node as 1, then add counts from left and right children recursively.

3

Call the function to count nodes

Call the function count_nodes with the root node root and store the result in a variable called total_nodes.

DSA Python

# Call count_nodes with root and save to total_nodes
# Your code here

Hint

Use the root node as the starting point to count all nodes.

4

Print the total number of nodes

Print the value of total_nodes to display the total number of nodes in the binary tree.

DSA Python

# Print the total_nodes variable
# Your code here

Hint

The tree has 5 nodes, so the printed output should be 5.

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