Get count Non-Leaf nodes in a Binary Tree

Problem statement:

You are given root node of a tree and you need to find the number of non leaf node in that tree.

Consider the image below:

Total number of non leaf node are 3.

This problem can by solved by traversing the tree and keep the count of number of non leaf nodes.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int get_non_leaf_node_count(struct Node* node) 
{ 
    // Base cases. 
    if (node == NULL || (node->left == NULL &&  
                         node->right == NULL)) 
        return 0; 
  
    return 1 + get_non_leaf_node_count(node->left) +  
               get_non_leaf_node_count(node->right); 
} 


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"Total number of Non leaf nodes are "<<get_non_leaf_node_count(root)<<endl;

    return 0;  
} 

Output:

Total number of Non leaf nodes are 3