Tutorialspoint.dev

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.



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 <bits/stdc++.h>
using namespace std;
  
// Represents a node of an n-ary tree
class Node {
  
public:
    int key;
    vector<Node*> 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<Node*> 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[0]->child).push_back(new Node(15));
    (root->child[0]->child).push_back(new Node(20));
    (root->child[1]->child).push_back(new Node(30));
    (root->child[2]->child).push_back(new Node(40));
    (root->child[2]->child).push_back(new Node(100));
    (root->child[2]->child).push_back(new Node(20));
    (root->child[0]->child[1]->child).push_back(new Node(25));
    (root->child[0]->child[1]->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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter