I cant seem to get my program to calculate the total leaves on a user input tree

Question

I cant seem to get my program to calculate the total leaves on a user input tree. Help please

// This program builds a binary tree with 5 nodes and calculates the number of leafs.
#include<iostream>
#include<cmath>
using namespace std;

struct node{
int data;
node *right, *left;
};

void insertNode(node* &head, int data){
if(head==NULL){
node *p = new node;
p->data = data;
p->left = NULL;
p->right = NULL;
head = p;
return;
}
if(data<=head->data){
if(head->left==NULL){
node *p = new node;
p->data = data;
p->left = NULL;
p->right = NULL;
head->left = p;
return;
}
insertNode(head->left, data);
}
else{
if(head->right==NULL){
node *p = new node;
p->data = data;
p->left = NULL;
p->right = NULL;
head->right = p;
return;
}
insertNode(head->right,data);
}
}

int height(node* root){
if(root==NULL)
return 0;
return max(height(root->left), height(root->right))+1;
}

bool isBalanced(node* root){
if(root==NULL)
return true;
int diff = height(root->left) - height(root->right);
if(abs(diff)>1)
return false;
else
return (isBalanced(root->left) && isBalanced(root->right));
}

//calculate the number of nodes in the tree
int NumberOfNodes(node * root){
if(!root)
return 0;

if(root->right == NULL && root->left == NULL)
return 1;
else{
return (NumberOfNodes(root->right) + NumberOfNodes(root->left) + 1);
}
}

int main(){
node *root;
root = NULL;
int count, i;
    count = 0;
   
  
//building the tree from the elements of the array.
//If you want the user to provide the input, you only need to read the inputs One by One and call the function insertNode
//with each input
for(int i=0; i<i<count; i++)
insertNode(root, count);
        cout << "Enter a node:"<<endl;
        cin >> i;
  
insertNode(root, count);
        cout << "Enter a node:"<<endl;
        cin >> i;
insertNode(root, count);
        cout << "Enter a node:"<<endl;
        cin >> i;

insertNode(root, count);
        cout << "Enter a node:"<<endl;
        cin >> i;
    insertNode(root, count);
        cout << "Enter a node:"<<endl;
        cin >> i;     
    insertNode(root, count);
        cout << "Enter a node:"<<endl;
        cin >> i;     
    for(int i=0; i<i<count; i++)
{
       cout << " The number of nodes entered are"<<endl;
       return 0;
             
}
}

Explanation / Answer

getLeafCount(node)

1)if node is NULL then return 0

2)else if right child nodes are NULL return 1.

3)recursively calculate leaf count of the tree using below formula.

Leaf count of a tree = Leaf count of left subtree +
Leaf count of right subtree

Example Tree
Example Tree

Leaf count for the above tree is 3.

Implementation:

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

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Function to get the count of leaf nodes in a binary tree*/
unsigned int getLeafCount(struct node* node)
{
if(node == NULL)   
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/*Driver program to test above functions*/
int main()
{
/*create a tree*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

/*get leaf count of the above created tree*/
printf("Leaf count of the tree is %d", getLeafCount

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.