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.