Number of siblings of a given Node in n-ary Tree

PseudoCode

Algorithm

___________________________________________________________________

procedure NumberOfSiblingsOfGivenNode(rootNode, x):

___________________________________________________________________

1.    Queue q ← an empty queue # to find the given node. 

2.    q.push(rootNode) 

3.    while q is not empty do

4.      topNode ←q.front()

5.          for all adjNode of topNode.children do

6.               if adjNode.value == x do

7.                   return topNode.children.size()

8.               end if

9.          end for

10.   end while 

11. end procedure

___________________________________________________________________

Implementation in C++

// program to find the number of siblings of a given Node in n-ary Tree
#include <bits/stdc++.h>
#define Node N_aryNode
using namespace std;


// node of a n-ary tree
struct N_aryNode{
    int val; // value stored
    vector<Node*> children; // children of a node
    N_aryNode(int x){
        this->val = x; // set the value of this node to x
    }
};



// function that returns the number of siblings of a given node x
int NumberOfSiblingsOfGivenNode(Node* root, int x){
    queue<Node*> q; // to store the node for traversing the tree
    q.push(root); // push the node
    
    // we will traverse each node until the queue is empty 
    while(!q.empty()){
        // compute the size of the queue so that we run  
        // for all children added in previous iteration
        int size = q.size();
        
        while(size--){
            Node* top = q.front();q.pop(); // pick the front node
            
            // return the number of siblings if current node matches x
            if(top->val==x) 
                return top->children.size()+1;
            
            // traverse over all children of the current node picked
            for(Node* child: top->children){
                q.push(child); //push it inside the queue
            }
        }
    }
    
    // return -1 just for the sake of returning
    return -1;
}


int main() {
    
    // create the N-ary tree    
    Node* root = new Node(1);
    root->children.push_back(new Node(2));
    root->children.push_back(new Node(12));
    root->children.push_back(new Node(11));
    root->children.push_back(new Node(21));
    
    root->children[0]->children.push_back(new Node(3));
    root->children[0]->children[0]->children.push_back(new Node(4));    
    
    root->children[0]->children.push_back(new Node(1));
    root->children[0]->children[1]->children.push_back(new Node(5));
    root->children[0]->children[1]->children.push_back(new Node(6));
    
    root->children[0]->children.push_back(new Node(11));
    root->children[0]->children[2]->children.push_back(new Node(9)); 
    
    root->children[0]->children.push_back(new Node(10));
    root->children[0]->children[3]->children.push_back(new Node(7));
    root->children[0]->children[3]->children.push_back(new Node(8));
    
    int x = 10;
    
    // get the answer
    int num_siblings = NumberOfSiblingsOfGivenNode(root, x);


    // print it
    cout<<"Number of Siblings of the given node "<<x<<" in the N-ary Tree are: "<<num_siblings;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Number of Siblings of the given node 10 in the N-ary Tree are: 3

Complexity Analysis

Time Complexity: O(n)

This is because we iterate through the entire n-ary tree once to find Number of siblings of a given Node in n-ary Tree. 

Space complexity: O(n) at the worst case because we are storing the children at each level inside a queue to find Number of siblings of a given Node in n-ary Tree.

Frequently Asked Questions

What are the multiple ways in which we can represent a graph?

We can store a graph in multiple ways. For example we have adjacency lists, adjacency matrix, edge lists etc. 

What is the time complexity of deletion inside a N-ary Tree?

The time complexity of insertion inside a N-ary Tree is O(n). 

How is level-order traversal different from DFS traversal?

Both the traversals are really different in nature, in the way they traverse the graph. So level-order traverses all nodes at level then moves to the next level, whereas dfs traversal traverses nodes to the depth.

Conclusion

This article taught us how to solve the problem to find the number of siblings of a given Node in n-ary Tree. We also saw how to approach the problem using examples and approach followed by a solution implementation. 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!