Written in C++, find the number of siblings of a given node in an N-ary tree

In this article, we will provide complete information to determine the number of siblings of a given node in an n-ary tree. We need to find the sibling nodes of this node using the key value given by the user; if not, output -1. We can use only one method -

Simple method

In this method we will iterate through all the nodes and check if the child nodes have the same value as the user. If present, we answer the number of child nodes - 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

Description of the above program

In this program, we maintain a queue containing unvisited nodes and will Pops up visited nodes. Now when we explore a node we explore its children and if the value of the child matches x then our flag is triggered and our answer variable has been assigned a value of child.size() - 1 and Then we break out of the for loop and now we check if the flag is triggered. If it fires, then we exit the while loop. After that, if there is no node with the given value, we now print the answer, so our answer variable does not change and the output will be -1. If the root value is the same as the given value, there is an if statement that checks the value and runs our program.

Conclusion

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

The above is the detailed content of Written in C++, find the number of siblings of a given node in an N-ary tree. For more information, please follow other related articles on the PHP Chinese website!