Number of nodes greater than a given value in n-ary tree in C++

Given an n-ary tree and a number, we have to count the number of nodes greater than the given number. Let's see an example.

Input

tree = [[4], [1, 2], [3, 5]] n = 2

Output

3

There are 3 nodes with values that are greater than n.

Algorithm

• Initialise the n-ary tree.

• Initialise the count to 0.

• Increment the count by 1 when you find a node whose value is greater than n.

• Get the children of the current node.

• Iterate over all the children and recursively call the same function to count nodes.

• Return the count.

Implementation

Following is the implementation of the above algorithm in C++

#include <bits/stdc++.h> using namespace std; struct Node {    int data;    vector<Node*> child; }; Node* getNewNode(int data) {    Node* temp = new Node;    temp->data = data;    return temp; } int getGreaterElementsCount(Node* root, int n) {    if (root == NULL)       return 0;    int count = 0;    if (root->data > n) {       count++;    }    int nodeChildrenCount = root->child.size();    for (int i = 0; i < nodeChildrenCount; i++) {       Node* child = root->child[i];       count += getGreaterElementsCount(child, n);    }    return count; } int main() {    Node* root = getNewNode(1);    (root->child).push_back(getNewNode(2));    (root->child).push_back(getNewNode(3));    (root->child).push_back(getNewNode(4));    (root->child[0]->child).push_back(getNewNode(5));    (root->child[0]->child).push_back(getNewNode(5));    (root->child[1]->child).push_back(getNewNode(6));    (root->child[1]->child).push_back(getNewNode(6));    (root->child[1]->child).push_back(getNewNode(7));    (root->child[2]->child).push_back(getNewNode(8));    (root->child[2]->child).push_back(getNewNode(8));    (root->child[2]->child).push_back(getNewNode(9));    int n = 2;    cout << getGreaterElementsCount(root, n) << endl;    return 0; }

Output

If you run the above code, then you will get the following result.

10