Find the Number of Siblings of a Given Node in N-ary Tree Using C++

In this article, we will provide complete information to determine the number of siblings of a given node in the n-ary tree. We need to find the node's siblings with the value of key as given by the user; if it is non, then output as -1. There is only one approach that we can use −

Simple Approach

In this approach, we will go through all the nodes and check if a child has the same value as the user. If it exists, we answer a number of children - 1(the given value).

Example

#include <bits/stdc++.h>
using namespace std;
class Node {  // structure of nodes of our tree.
public:
    int key;
    vector<Node*> child;
    Node(int data){
        key = data;
    }
};
int main(){
   //     Building The Tree
    Node* Base = new Node(50);
    (Base->child).push_back(new Node(2));
    (Base->child).push_back(new Node(30));
    (Base->child).push_back(new Node(14));
    (Base->child).push_back(new Node(60));
    (Base->child[0]->child).push_back(new Node(15));
    (Base->child[0]->child).push_back(new Node(25));
    (Base->child[0]->child[1]->child).push_back(new Node(70));
    (Base->child[0]->child[1]->child).push_back(new Node(100));
    (Base->child[1]->child).push_back(new Node(6));
    (Base->child[1]->child).push_back(new Node(1));
    (Base->child[2]->child).push_back(new Node(7));
    (Base->child[2]->child[0]->child).push_back(new Node(17));
    (Base->child[2]->child[0]->child).push_back(new Node(99));
    (Base->child[2]->child[0]->child).push_back(new Node(27));
    (Base->child[3]->child).push_back(new Node(16));
    int x = 30;
    queue<Node*> q;
    q.push(Base);
    bool flag = 0;
    int answer = -1;
    if(Base -> key != x){
        while(!q.empty()){
            auto parent = q.front();
            q.pop();
            for(int i = 0; i < parent -> child.size(); i++){
                if(parent -> child[i] -> key == x){
                    answer = parent -> child.size() - 1;
                    flag = 1;
                    break;
                }
                q.push(parent -> child[i]);
            }
            if(flag)
                break;
        }
        cout << answer << "\n";
    }
    else
        cout << "0\n";
    return 0;
}

Output

3

Explanation of the Above Program

In this program, we maintain a queue that will have the unvisited nodes inside it, and the visited node will be popped. Now, when we explore a node, we explore its children, and if the value of the child matches to x, then our flag is triggered, and our answer variable has been assigned the value of the child.size() - 1, and then we break through the for a loop now we check if the flag is triggered or not. If it is triggered, then we come out of the while loop. After that, we print the answer now if there doesn't exist a node with the given value, so then our answer variable will not change, and the output will be -1. If the root value has the same value as given, there is an if statement that checks that and runs our program.

Conclusion

In this article, we solve a problem to find the number of siblings of a given node in n-ary tree in O(N) time complexity. We also learned the C++ program for this problem and the complete approach by which we solved this problem. We can write the same program in other languages such as C, java, python, and other languages.