3.4) Count Nodes in Complete Binary Tree

Given a complete Binary Tree, write a function to count and return the total number of nodes present in the tree.

A complete Binary Tree is a binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.

Consider the following complete Binary Tree:

        10
       /  \
      8    15
     / \   /
    3   5 12

The total number of nodes in the given complete Binary Tree is 6.

C++ Solution:

#include <iostream>

// Define a node structure for the Binary Tree
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to calculate the height of a complete Binary Tree
int calculateHeight(Node* root) {
    int height = 0;
    while (root) {
        height++;
        root = root->left;
    }
    return height;
}

// Function to count nodes in a complete Binary Tree
int countNodes(Node* root) {
    if (root == nullptr)
        return 0;

    int leftHeight = calculateHeight(root->left);
    int rightHeight = calculateHeight(root->right);

    // If left and right heights are equal, it means the left subtree is complete
    if (leftHeight == rightHeight) {
        return (1 << leftHeight) + countNodes(root->right); // 2^leftHeight
    } else {
        // If left and right heights are not equal, it means the right subtree is complete
        return (1 << rightHeight) + countNodes(root->left); // 2^rightHeight
    }
}

int main() {
    // Creating the complete Binary Tree
    Node* root = new Node(10);
    root->left = new Node(8);
    root->right = new Node(15);
    root->left->left = new Node(3);
    root->left->right = new Node(5);
    root->right->left = new Node(12);

    // Count and print the total number of nodes in the complete Binary Tree
    int nodeCount = countNodes(root);
    std::cout << "Total number of nodes in the complete Binary Tree: " << nodeCount << std::endl;

    return 0;
}

Time and Space Complexity:

The time complexity of counting nodes in a complete Binary Tree is O(log n * log n), where n is the number of nodes in the tree. The space complexity is O(h), where h is the height of the tree, due to the space used by the recursive function call stack.

Code Explanation:

In above code, we use the property of a complete binary tree that the total number of nodes in a full complete binary tree is 2^h-1. By definition, a complete tree must be filled up to the second last level, as the last level may or may not be filled, but all the leaf nodes will be on as much left position as possible.

So, we will start with the root and calculate the tree’s height in both the left and right directions. If the heights are equal, then the number of nodes will 2^h-1.

Otherwise, we will repeat the process for left and right subtrees and return the sum of (nodes in left subtree) + (nodes in right subtree) + 1 (for the root) as the count.

Steps:

• We define a Node structure for the Binary Tree, holding data, a left child, and a right child.
• The calculateHeight function calculates the height of a complete Binary Tree. It counts the number of levels from the root node to the leftmost leaf.
• The countNodes function recursively counts the nodes in the complete Binary Tree. It calculates the heights of the left and right subtrees, and based on their heights, determines whether the left or right subtree is complete. It then calculates the number of nodes in the complete subtree and continues the process for the remaining part of the tree.
• In the main function, we create the complete Binary Tree and call countNodes to calculate and print the total number of nodes in the tree.

When you run the code, it calculates and prints the total number of nodes in the given complete Binary Tree, which is 6 in this case.