Count Nodes in Binary Tree

#include <stdio.h>
#include <stdlib.h>

// Define a structure for the nodes in the binary tree
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to count the nodes in the binary tree
int countNodes(struct Node* root) {
    // Base case: If the tree is empty, return 0
    if (root == NULL)
        return 0;
    // Recursively count nodes in left and right subtrees, and add 1 for the current node
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    // Create the root node and other nodes
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    // Count the total number of nodes in the binary tree
    int totalNodes = countNodes(root);
    printf("Total number of nodes in the binary tree: %d\n", totalNodes);

    return 0;
}

Explanation

Step 1: Structure Definition

• Node Structure: A structure named Node is defined to represent each node in the binary tree. It has three fields:
  • data: Holds the integer value for the node.
  • left: A pointer to the left child of the node.
  • right: A pointer to the right child of the node.

Step 2: Creating a New Node

• createNode() Function: This function takes an integer value as input, creates a new node using malloc, sets its data field to the given value, and initializes its left and right pointers to NULL.

Step 3: Counting Nodes

• countNodes() Function: This recursive function calculates the total number of nodes in the tree.
  • Base Case: If the root is NULL, it means the tree is empty or a subtree is finished, so it returns 0.
  • Recursive Case: For non-empty trees, it recursively calls countNodes for the left and right children and adds 1 for the current node. The expression 1 + countNodes(root->left) + countNodes(root->right) is used to add up nodes from both subtrees and the current node.

Step 4: Main Function and Tree Creation

• In the main() function:
  • The root node and other nodes are created to form the binary tree.
  • The tree structure looks like this:

    1
   / \
  2   3
 / \ / \
4  5 6  7

The countNodes() function is called with the root of the tree, and the result is printed.

Output

When you run this program, the output will be:

Total number of nodes in the binary tree: 7

Explanation of the Output

The given binary tree has 7 nodes:

• Node 1 (root)
• Nodes 2 and 3 (children of 1)
• Nodes 4 and 5 (children of 2)
• Nodes 6 and 7 (children of 3)

The countNodes() function counts each of these nodes, resulting in a total of 7.