Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
3.
PseudoCode
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are the multiple ways in which we can represent a graph?
4.2.
What is the time complexity of deletion inside a N-ary Tree?
4.3.
How is level-order traversal different from DFS traversal?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Author aniket verma
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss how to find the number of siblings of a given Node in n-ary Tree. Such problems are fairly common interview questions as well asked in many contests. Before solving the problem, it’s recommended to have a good understanding of n-ary trees. In this Blog we will dive deep into each detail to get a firm hold over such kind of problems.  

Problem Statement

Give a node x and a n-ary tree. It’s assumed that node x exists in the tree. You need to find the number of siblings of a given Node in n-ary Tree.

Sample Example

Input:  

The input node is 10.

Output 3

Explanation:  the node 10 contains 3 siblings 21, 7 and 8 and hence the number of siblings of a given Node in n-ary Tree is 3.

Approach

The approach to this problem is very intuitive from problem statement itself. The number of siblings of a node would be the number of edges connected with its adjacent neighbours which will lead to our answer.

NOTE:-  this solutions to this problem can be implemented in multiple ways using adjacency lists, or creating node pointers where we can just store the root of the tree.

So the basic approach could be formulated as:

  1. Find the node using a dfs traversal or a bfs traversal.
  2. Return the number of adjacent neighbours connected to the node.

 

Now let’s look at the PseudoCode.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

PseudoCode

Algorithm

___________________________________________________________________

procedure NumberOfSiblingsOfGivenNode(rootNode, x):

___________________________________________________________________

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

2.    q.push(rootNode) 

3.    while 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;
}

 

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 AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine 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 problemsinterview 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!!

Previous article
Maximum Level Sum in N-ary Tree
Next article
Kth ancestor of a node in a binary tree
Live masterclass