Question

Consider the following struct that represents a node within a binary tree:

struct Node {
int data; // Data of interest
Node *left // Link to left subtree (nullptr if none)
Node *right ; // Link to right subtree (nullptr if none)
};

Complete the following function that computes the number of elements in a binary tree:

// Counts the number of elements in the binary tree to which t points.
// Returns the number of elements.
int size(Node *t) {





}

GIven root, a pointer to the root of a binary tree, size(root) evaluates to the number of nodes in the tree.

Answer 1

The required code and corresponding output are as follows:

#include <stdio.h>
#include<math.h>
 
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};
 
struct Node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */
  struct Node* newNode = 
        (struct Node*)malloc(sizeof(struct Node));
  
  /* include data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
   
  return newNode;
}
// Creating a binary tree to check the function size()
struct Node* generateBTree(){
    // Root Node
    struct Node* root =  getNewNode(1);
    // Level 2 nodes 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
    // Level 3 nodes
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);
     
    return root;
 
}
/*
Returns total number of nodes(size) in a bianry tree
size(root) = size(left-subTree) + 1 
                     + size(right-subTree);
*/
//Required Function
int size(struct Node *t){
    if(t == NULL)
        return 0;
    return size(t->left) + 1 + size(t->right);
}
 
int main() {
    struct Node *root = generateBTree();    
     
    printf("Size of Tree = %d", size(root));
     
    getchar();
    return 0; 
}

Output: