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