# Number of children of given node in n-ary Tree

Given a node x, find the number of children of x(if it exists) in the given n-ary tree. Example :

```Input : x = 50
Output : 3
Explanation : 50 has 3 children having values 40, 100 and 20.
```

## Recommended : Please try your approach on {IDE} first, before moving on to the solution.

Approach :

• Initialize the number of children as 0.
• For every node in the n-ary tree, check if its value is equal to x or not. If yes, then return the number of children.
• If the value of x is not equal to the current node then, push all the children of current node in the queue.
• Keep Repeating the above step until the queue becomes empty.

Below is the implementation of the above idea :

 `// C++ program to find number ` `// of children of given node ` `#include ` `using` `namespace` `std; ` ` `  `// Represents a node of an n-ary tree ` `class` `Node { ` ` `  `public``: ` `    ``int` `key; ` `    ``vector child; ` ` `  `    ``Node(``int` `data) ` `    ``{ ` `        ``key = data; ` `    ``} ` `}; ` ` `  `// Function to calculate number ` `// of children of given node ` `int` `numberOfChildren(Node* root, ``int` `x) ` `{ ` `    ``// initialize the numChildren as 0 ` `    ``int` `numChildren = 0; ` ` `  `    ``if` `(root == NULL) ` `        ``return` `0; ` ` `  `    ``// Creating a queue and pushing the root ` `    ``queue q; ` `    ``q.push(root); ` ` `  `    ``while` `(!q.empty()) { ` `        ``int` `n = q.size(); ` ` `  `        ``// If this node has children ` `        ``while` `(n > 0) { ` ` `  `            ``// Dequeue an item from queue and ` `            ``// check if it is equal to x ` `            ``// If YES, then return number of children ` `            ``Node* p = q.front(); ` `            ``q.pop(); ` `            ``if` `(p->key == x) { ` `                ``numChildren = numChildren + p->child.size(); ` `                ``return` `numChildren; ` `            ``} ` ` `  `            ``// Enqueue all children of the dequeued item ` `            ``for` `(``int` `i = 0; i < p->child.size(); i++) ` `                ``q.push(p->child[i]); ` `            ``n--; ` `        ``} ` `    ``} ` `    ``return` `numChildren; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``// Creating a generic tree ` `    ``Node* root = ``new` `Node(20); ` `    ``(root->child).push_back(``new` `Node(2)); ` `    ``(root->child).push_back(``new` `Node(34)); ` `    ``(root->child).push_back(``new` `Node(50)); ` `    ``(root->child).push_back(``new` `Node(60)); ` `    ``(root->child).push_back(``new` `Node(70)); ` `    ``(root->child->child).push_back(``new` `Node(15)); ` `    ``(root->child->child).push_back(``new` `Node(20)); ` `    ``(root->child->child).push_back(``new` `Node(30)); ` `    ``(root->child->child).push_back(``new` `Node(40)); ` `    ``(root->child->child).push_back(``new` `Node(100)); ` `    ``(root->child->child).push_back(``new` `Node(20)); ` `    ``(root->child->child->child).push_back(``new` `Node(25)); ` `    ``(root->child->child->child).push_back(``new` `Node(50)); ` ` `  `    ``// Node whose number of ` `    ``// children is to be calculated ` `    ``int` `x = 50; ` ` `  `    ``// Function calling ` `    ``cout << numberOfChildren(root, x) << endl; ` ` `  `    ``return` `0; ` `} `

Output:

```3
```

Time Complexity : O(N), where N is the number of nodes in tree.
Auxiliary Space : O(N), where N is the number of nodes in tree.

## tags:

Tree n-ary-tree Tree