Count Total Nodes in Binary Tree in DSA C++ - Build from Scratch

Count Total Nodes in Binary Tree

📖 Scenario: You are working with a simple binary tree data structure. Each node has a value and can have up to two children: left and right. You want to count how many nodes are in the entire 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 binary tree with exactly 5 nodes with given values

Use a recursive function to count total nodes in the tree

Print the total count of nodes

💡 Why This Matters

🌍 Real World

Counting nodes in a binary tree is a basic operation used in many applications like file systems, expression parsing, and decision trees.

💼 Career

Understanding tree structures and recursion is essential for software developers working with data structures, algorithms, and system design.

1

Create the Binary Tree Nodes

Create a struct called Node with an int data member, and two Node* members called left and right. Then create 5 nodes named root, node1, node2, node3, and node4. Initialize their data values to 10, 20, 30, 40, and 50 respectively. Set all left and right pointers to nullptr.

DSA C++

// Define struct Node and create 5 nodes with given data and nullptr children
// Your code here

Hint

Define the struct with three members. Then create each node using curly braces to set data and pointers.

2

Link the Nodes to Form the Tree

Link the nodes to form this binary tree structure: root.left = &node1, root.right = &node2, node1.left = &node3, and node1.right = &node4. Keep other pointers as nullptr.

DSA C++

#include 

struct Node {
    int data;
    Node* left;
    Node* right;
};

int main() {
    Node root{10, nullptr, nullptr};
    Node node1{20, nullptr, nullptr};
    Node node2{30, nullptr, nullptr};
    Node node3{40, nullptr, nullptr};
    Node node4{50, nullptr, nullptr};

    // Link nodes to form the tree
    // Your code here

    return 0;
}

Hint

Assign the pointers to connect nodes as described.

3

Write a Recursive Function to Count Nodes

Write a recursive function called countNodes that takes a Node* parameter called root. It returns 0 if root is nullptr. Otherwise, it returns 1 + countNodes(root->left) + countNodes(root->right).

DSA C++

#include 

struct Node {
    int data;
    Node* left;
    Node* right;
};

// Write the countNodes function here
// Your code here

int main() {
    Node root{10, nullptr, nullptr};
    Node node1{20, nullptr, nullptr};
    Node node2{30, nullptr, nullptr};
    Node node3{40, nullptr, nullptr};
    Node node4{50, nullptr, nullptr};

    root.left = &node1;
    root.right = &node2;
    node1.left = &node3;
    node1.right = &node4;

    return 0;
}

Hint

Use a base case for nullptr and recursive calls for left and right children.

4

Print the Total Number of Nodes

In main, call countNodes with &root and store the result in an int variable called totalNodes. Then print "Total nodes: " followed by totalNodes using std::cout.

DSA C++

#include 

struct Node {
    int data;
    Node* left;
    Node* right;
};

int countNodes(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    Node root{10, nullptr, nullptr};
    Node node1{20, nullptr, nullptr};
    Node node2{30, nullptr, nullptr};
    Node node3{40, nullptr, nullptr};
    Node node4{50, nullptr, nullptr};

    root.left = &node1;
    root.right = &node2;
    node1.left = &node3;
    node1.right = &node4;

    // Call countNodes and print the result
    // Your code here

    return 0;
}

Hint

Store the count in totalNodes and print it with std::cout.

Practice

1. What does the function countNodes do in a binary tree?

easy

A. Checks if the binary tree is balanced

B. Finds the height of the binary tree

C. Calculates the sum of all node values

D. Counts the total number of nodes in the binary tree

Solution

1. Step 1: Understand the function purpose

   The function countNodes is designed to traverse the binary tree and count every node it visits.

2. Step 2: Differentiate from other tree functions

   Unlike functions that find height, sum values, or check balance, this function specifically returns the total count of nodes.

3. Final Answer:

   Counts the total number of nodes in the binary tree -> Option D

4. Quick Check:

   Counting nodes = total nodes [OK]

Hint: Count nodes by visiting each once [OK]

Common Mistakes:

• Confusing node count with tree height
• Thinking it sums node values
• Assuming it checks tree balance

2. Which of the following is the correct base case for a recursive function counting nodes in a binary tree?

easy

A. if (root == nullptr) return 0;

B. if (root == nullptr) return 1;

C. if (root == nullptr) return -1;

D. if (root == nullptr) return root->data;

Solution

1. Step 1: Identify base case for recursion

   When the current node is null (no node), the count should be zero because there is no node to count.

2. Step 2: Check each option

   if (root == nullptr) return 0; returns 0 for null nodes, which is correct. Other options return incorrect values for base case.

3. Final Answer:

   if (root == nullptr) return 0; -> Option A

4. Quick Check:

   Null node count = 0 [OK]

Hint: Return 0 when node is null [OK]

Common Mistakes:

• Returning 1 for null node
• Returning node data in base case
• Returning negative values

3. What is the output of the following code snippet?

struct Node {
  int data;
  Node* left;
  Node* right;
};

int countNodes(Node* root) {
  if (root == nullptr) return 0;
  return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
  Node n1 = {1, nullptr, nullptr};
  Node n2 = {2, nullptr, nullptr};
  Node n3 = {3, &n1, &n2};
  std::cout << countNodes(&n3);
  return 0;
}

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Analyze the tree structure

   Node n3 is root with left child n1 and right child n2. Both n1 and n2 have no children.

2. Step 2: Count nodes recursively

   countNodes(n3) = 1 + countNodes(n1) + countNodes(n2) = 1 + 1 + 1 = 3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3 nodes counted [OK]

Hint: Add 1 for current node plus children counts [OK]

Common Mistakes:

• Counting only root node
• Ignoring one child subtree
• Returning zero for non-null root

4. Find the error in this code snippet for counting nodes in a binary tree:

int countNodes(Node* root) {
  if (root == nullptr) return 0;
  return countNodes(root->left) + countNodes(root->right);
}

medium

A. Missing addition of 1 for current node

B. Base case returns 1 instead of 0

C. Function does not handle nullptr correctly

D. No error, code is correct

Solution

1. Step 1: Check base case correctness

   Base case returns 0 for nullptr, which is correct.

2. Step 2: Check counting logic

   The function sums counts of left and right subtrees but does not add 1 for the current node itself, missing counting the root.

3. Final Answer:

   Missing addition of 1 for current node -> Option A

4. Quick Check:

   Count must include current node [OK]

Hint: Add 1 for current node in return [OK]

Common Mistakes:

• Returning 1 for null node
• Not adding 1 for current node
• Confusing base case return value

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. 14

B. 13

C. 15

D. 16

Solution

1. Step 1: Recall property of full binary trees

   In a full binary tree (nodes have 0 or 2 children), total nodes = 2 * leaf nodes - 1.

2. Step 2: Calculate total nodes

   Given leaf nodes = 7, total nodes = 2 * 7 - 1 = 13.

3. Step 3: Verify formula and options

   Formula: total nodes = 2 * leaf nodes - 1 = 2*7 -1 = 13, which matches 13.

4. Final Answer:

   13 -> Option B

5. Quick Check:

   Full binary tree nodes = 2*leaves - 1 [OK]

Hint: Use full tree formula: nodes = 2*leaves - 1 [OK]

Common Mistakes:

• Using wrong formula for total nodes
• Confusing leaf nodes with total nodes
• Selecting option without calculation