{"id":671,"date":"2024-10-10T13:40:00","date_gmt":"2024-10-10T08:10:00","guid":{"rendered":"https:\/\/codexplained.in\/?p=671"},"modified":"2025-11-24T15:58:15","modified_gmt":"2025-11-24T10:28:15","slug":"count-nodes-in-binary-tree","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=671","title":{"rendered":"Count Nodes in Binary Tree"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Define a structure for the nodes in the binary tree\nstruct Node {\n    int data;\n    struct Node* left;\n    struct Node* right;\n};\n\n\/\/ Function to create a new node\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->data = data;\n    newNode->left = NULL;\n    newNode->right = NULL;\n    return newNode;\n}\n\n\/\/ Function to count the nodes in the binary tree\nint countNodes(struct Node* root) {\n    \/\/ Base case: If the tree is empty, return 0\n    if (root == NULL)\n        return 0;\n    \/\/ Recursively count nodes in left and right subtrees, and add 1 for the current node\n    return 1 + countNodes(root->left) + countNodes(root->right);\n}\n\nint main() {\n    \/\/ Create the root node and other nodes\n    struct Node* root = createNode(1);\n    root->left = createNode(2);\n    root->right = createNode(3);\n    root->left->left = createNode(4);\n    root->left->right = createNode(5);\n    root->right->left = createNode(6);\n    root->right->right = createNode(7);\n\n    \/\/ Count the total number of nodes in the binary tree\n    int totalNodes = countNodes(root);\n    printf("Total number of nodes in the binary tree: %d\\n", totalNodes);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation<\/h2>\n\n\n\n
Step 1: Structure Definition<\/h3>\n\n\n\n
    \n
  • Node Structure<\/strong>: A structure named Node<\/code> is defined to represent each node in the binary tree. It has three fields:\n
      \n
    • data<\/code>: Holds the integer value for the node.<\/li>\n\n\n\n
    • left<\/code>: A pointer to the left child of the node.<\/li>\n\n\n\n
    • right<\/code>: A pointer to the right child of the node.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
      Step 2: Creating a New Node<\/h3>\n\n\n\n
        \n
      • createNode()<\/code> Function<\/strong>: This function takes an integer value as input, creates a new node using malloc<\/code>, sets its data<\/code> field to the given value, and initializes its left<\/code> and right<\/code> pointers to NULL<\/code>.<\/li>\n<\/ul>\n\n\n\n
        Step 3: Counting Nodes<\/h3>\n\n\n\n
          \n
        • countNodes()<\/code> Function<\/strong>: This recursive function calculates the total number of nodes in the tree.\n
            \n
          • Base Case<\/strong>: If the root<\/code> is NULL<\/code>, it means the tree is empty or a subtree is finished, so it returns 0<\/code>.<\/li>\n\n\n\n
          • Recursive Case<\/strong>: For non-empty trees, it recursively calls countNodes<\/code> for the left and right children and adds 1<\/code> for the current node. The expression 1 + countNodes(root->left) + countNodes(root->right)<\/code> is used to add up nodes from both subtrees and the current node.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
            Step 4: Main Function and Tree Creation<\/h3>\n\n\n\n
              \n
            • In the main()<\/code> function:\n
                \n
              • The root node and other nodes are created to form the binary tree.<\/li>\n\n\n\n
              • The tree structure looks like this:<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                    1\n   \/ \\\n  2   3\n \/ \\ \/ \\\n4  5 6  7\n<\/code><\/pre>\n\n\n\n
                The countNodes()<\/code> function is called with the root of the tree, and the result is printed.<\/p>\n\n\n\n
                Output<\/h2>\n\n\n\n
                When you run this program, the output will be:<\/p>\n\n\n\n
                Total number of nodes in the binary tree: 7\n<\/code><\/pre>\n\n\n\n
                Explanation of the Output<\/h3>\n\n\n\n
                The given binary tree has 7 nodes:<\/p>\n\n\n\n
                  \n
                • Node 1<\/code> (root)<\/li>\n\n\n\n
                • Nodes 2<\/code> and 3<\/code> (children of 1<\/code>)<\/li>\n\n\n\n
                • Nodes 4<\/code> and 5<\/code> (children of 2<\/code>)<\/li>\n\n\n\n
                • Nodes 6<\/code> and 7<\/code> (children of 3<\/code>)<\/li>\n<\/ul>\n\n\n\n
                  The countNodes()<\/code> function counts each of these nodes, resulting in a total of 7<\/code>.<\/p>\n