C++ program to count leaf nodes in a binary tree using recursion














































C++ program to count leaf nodes in a binary tree using recursion



/**C++ program to count leaf nodes in a binary tree using recursion**/
/**For calculating total no of leaf node we may use recursive method.
Within recursive call if we get any node whose left and right child
both are null then we call that node as leaf node. Using recursive
method if we get such type of node then we will simply increment a
counter that count total no of leaf node.

              10
            /    \
         11      9
         /   \   /   \
     7    12 11    8

As in this programme we need to check for each node so that time
complexity for that programme will be O(n) where n is the total no
of node of the binary tree.**/
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
    int data;
    struct Node* left, *right;
};
struct Node* newNode(int value)
{
    struct Node* temp =new Node;
    temp->data = value;
    temp->left = temp->right = NULL;
    return temp;
};
/**insertion of new node in a binary tree**/
void insert(struct Node* temp, int value)
{
    queue<struct Node*> q;
    q.push(temp);
    while(!q.empty())
    {
        struct Node* temp = q.front();
        q.pop();
        if(!temp->left)
        {
            temp->left = newNode(value);
            break;
        }
        else
            q.push(temp->left);
        if (!temp->right)
        {
            temp->right = newNode(value);
            break;
        }
        else
            q.push(temp->right);
    }
}
/**calculate sum of value of all leaf node**/
int sum(struct Node* root,int s)
{
    struct Node *temp=root;
    if(temp->left==nullptr && temp->right==nullptr)
        return (s+1);
    else
    {
        s=sum(temp->left,s);
        s=sum(temp->right,s);
    }
    return s;
}
int main()
{
    int value,t,s;
    struct Node* root = newNode(10);                    //insertion of element;
    root->left = newNode(11);
    root->left->left = newNode(7);
    root->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(8);
    t = 12;
    insert(root,t);
    cout << "Total no of leaf node is:\n";
    s=sum(root,0);
    cout << s;
    return 0;
}
/**
    Output:
    Total no of leaf node is:
    4
**/


More Articles of Ezaz Hossain Sardar:

Name Views Likes
Python Program to Find the first Common Element between the 2 given Linked Lists 254 20
C++ std::valarray_function_name 320 23
C++ std::typeindex_function_name 220 14
C++ std::condition_variable 298 16
C++ mutex mutex_function_name 298 24
C++ std:: 234 20
C++ std::is_trivially_default_constructible 294 20
C++ std::is_trivially_copy_constructible 302 29
C++ std::is_signed 294 25
C++ std::is_scalar 246 15
C++ std::is_same 323 22
C++ std::is_rvalue_reference 269 15
C++ std::is_reference 212 17
C++ std::is_object 257 15
C++ std::is_nothrow_destructible 334 26
C++ std::is_nothrow_constructible 300 22
C++ std::is_member_pointer 240 16
C++ std::is_member_function_pointer 263 19
C++ std::is_literal_type 305 26
C++ std::is_fundamental 261 16
C++ std::is_compound 267 20
C++ std::move for list 297 29
C++ std::move for array 287 22
C++ std::move 273 20
C++ std::replace for array 853 17
C++ std::replace 295 20
C++ std::replace_if 296 22
C++ std::minmax 325 27
C++ std::minmax_element 299 11
C++ std::remove 241 12
C++ std::remove_if 265 18
C++ std::replace_copy 253 20
C++ std::replace_copy_if 234 11
C++ std::remove_copy 271 19
C++ program to find get level of a node in binary tree using recursion 273 28
C++ program to find size of a tree without using recursion 202 14
C++ program to find height of a tree without using recursion 210 17
C++ program to find diameter of a binary tree in O(n) 269 23
C++ program to find diameter of a binary tree 245 13
C++ program to find height of a tree using recursion 215 17
C++ program to count non-leaf nodes in a binary tree using recursion 320 19
C++ program to count leaf nodes in a binary tree using recursion 672 13
C++ program to find sum of all leaf nodes of binary tree 250 21
C++ program to find sum of all the parent nodes having child node x 402 23
C++ program to print path from root to a given node in a binary tree 245 16
C++ program to find distance from root to given node in a binary tree 264 18

Comments