## Problem statement:

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

A node will be considered as full node if it has both left and right child.

Consider the image below:

Total number of full nodes are 3.

This problem can by solved by traversing the tree and keep the count of the nodes that is having both left and right children.

## 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_full_node_count(struct Node* node) { if (node == NULL) return 0; int result = 0; if (node->left && node->right) result++; result += (get_full_node_count(node->left) + get_full_node_count(node->right)); return result; } 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 full nodes are "<<get_full_node_count(root)<<endl; return 0; }

## Output:

Total number of full nodes are 3