Print siblings of a given Node in N-ary Tree
Given an N-ary tree and an element X, the task is to print the siblings of the node with value X.
Two nodes are considered to be siblings if they are present at the same level and have the same parent.
Examples:
Input: X = 100
Output: 90 110
Explanation: Nodes valued 90, 100 and 110 have the same parent, i.e. the node valued 40. Therefore, nodes 90 and 110 are the siblings of the given node X( = 100).Input: X = 30
Output: 20 40
Explanation: Nodes valued 20, 30 and 40 have the same parent, i.e. the node valued 10. Therefore, nodes 20 and 40 are the siblings of the given node X( = 30).
Approach: Follow the steps given below to solve the problem:
- Perform level order traversal on the given N-ary tree.
- Initialize a queue q for level order traversal.
- For every node encountered, push all its children into the queue.
- While pushing the children of the current node into the queue, check: if any of these children is equal to the given value X or not. If found to be true, then print all nodes except X which are children of the current as the required answer.
- Otherwise, continue to traversing the tree.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of a node of N-ary tree struct Node { int key; vector<Node*> child; }; // Function to create a new node Node* newNode( int key) { Node* temp = new Node; temp->key = key; return temp; } // Function to find the siblings // of the node value void Siblings(Node* root, int value) { int flag = 0; if (root == NULL) return ; // Stores nodes level wise queue<Node*> q; // Push the root q.push(root); // Continue until all levels // are traversed while (!q.empty()) { // Stores current node Node* temp = q.front(); q.pop(); // Enqueue all children of the current node for ( int i = 0; i < temp->child.size(); i++) { // If node value is found if (temp->child[i]->key == value) { flag = 1; // Print all children of current node // except value as the answer for ( int j = 0; j < temp->child.size(); j++) { if (value != temp->child[j]->key) cout << temp->child[j]->key << " " ; } break ; } // Push the child nodes // of temp into the queue q.push(temp->child[i]); } } if (flag == 0) cout << "No siblings!!" ; } Node* constructTree() { Node* root = newNode(10); (root->child).push_back(newNode(20)); (root->child).push_back(newNode(30)); (root->child).push_back(newNode(40)); (root->child[0]->child).push_back(newNode(50)); (root->child[0]->child).push_back(newNode(60)); (root->child[1]->child).push_back(newNode(70)); (root->child[1]->child).push_back(newNode(80)); (root->child[2]->child).push_back(newNode(90)); (root->child[2]->child).push_back(newNode(100)); (root->child[2]->child).push_back(newNode(110)); return root; } // Driver Code int main() { // Stores root of the // constructed tree Node* root = constructTree(); int X = 30; // Print siblings of Node X Siblings(root, X); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Structure of a node // of N-ary tree static class Node { int key; Vector<Node> child = new Vector<>(); }; // Function to create a // new node static Node newNode( int key) { Node temp = new Node(); temp.key = key; return temp; } // Function to find the // siblings of the node /// value static void Siblings(Node root, int value) { int flag = 0 ; if (root == null ) return ; // Stores nodes level wise Queue<Node> q = new LinkedList<>(); // Push the root q.add(root); // Continue until all // levels are traversed while (!q.isEmpty()) { // Stores current node Node temp = q.peek(); q.remove(); // Enqueue all children // of the current node for ( int i = 0 ; i < temp.child.size(); i++) { // If node value is found if (temp.child.get(i).key == value) { flag = 1 ; // Print all children of current // node // except value as the answer for ( int j = 0 ; j < temp.child.size(); j++) { if (value != temp.child.get(j).key) System.out.print( temp.child.get(j).key + " " ); } break ; } // Push the child nodes // of temp into the queue q.add(temp.child.get(i)); } } if (flag == 0 ) System.out.print( "No siblings!!" ); } static Node constructTree() { Node root = newNode( 10 ); (root.child).add(newNode( 20 )); (root.child).add(newNode( 30 )); (root.child).add(newNode( 40 )); (root.child.get( 0 ).child).add(newNode( 50 )); (root.child.get( 0 ).child).add(newNode( 60 )); (root.child.get( 1 ).child).add(newNode( 70 )); (root.child.get( 1 ).child).add(newNode( 80 )); (root.child.get( 2 ).child).add(newNode( 90 )); (root.child.get( 2 ).child).add(newNode( 100 )); (root.child.get( 2 ).child).add(newNode( 110 )); return root; } // Driver Code public static void main(String[] args) { // Stores root of the // constructed tree Node root = constructTree(); int X = 30 ; // Print siblings of Node X Siblings(root, X); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 code for the above approach from collections import deque # Class to represent a node of N-ary tree class Node: def __init__( self , key): self .key = key self .child = [] # Function to create a new node def newNode(key): temp = Node(key) return temp # Function to find the siblings # of the node value def Siblings(root, value): flag = 0 if root is None : return # Stores nodes level wise q = deque() # Push the root q.append(root) # Continue until all levels # are traversed while len (q) > 0 : # Stores current node temp = q.popleft() # Enqueue all children of the current node for i in range ( len (temp.child)): # If node value is found if temp.child[i].key = = value: flag = 1 # Print all children of current node # except value as the answer for j in range ( len (temp.child)): if value ! = temp.child[j].key: print (temp.child[j].key, end = " " ) break # Push the child nodes # of temp into the queue q.append(temp.child[i]) if flag = = 0 : print ( "No siblings!!" ) def constructTree(): root = newNode( 10 ) root.child.append(newNode( 20 )) root.child.append(newNode( 30 )) root.child.append(newNode( 40 )) root.child[ 0 ].child.append(newNode( 50 )) root.child[ 0 ].child.append(newNode( 60 )) root.child[ 1 ].child.append(newNode( 70 )) root.child[ 1 ].child.append(newNode( 80 )) root.child[ 2 ].child.append(newNode( 90 )) root.child[ 2 ].child.append(newNode( 100 )) root.child[ 2 ].child.append(newNode( 110 )) return root # Driver Code if __name__ = = '__main__' : # Stores root of the # constructed tree root = constructTree() X = 30 # Print siblings of Node X Siblings(root, X) # This code is contributed by Potta Lokesh |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Structure of a node // of N-ary tree public class Node { public int key; public List<Node> child = new List<Node>(); }; // Function to create a // new node static Node newNode( int key) { Node temp = new Node(); temp.key = key; return temp; } // Function to find the // siblings of the node /// value static void Siblings(Node root, int value) { int flag = 0; if (root == null ) return ; // Stores nodes level // wise Queue<Node> q = new Queue<Node>(); // Push the root q.Enqueue(root); // Continue until all // levels are traversed while (q.Count != 0) { // Stores current node Node temp = q.Peek(); q.Dequeue(); // Enqueue all children // of the current node for ( int i = 0; i < temp.child.Count; i++) { // If node value is found if (temp.child[i].key == value) { flag = 1; // Print all children of // current node except value // as the answer for ( int j = 0; j < temp.child.Count; j++) { if (value != temp.child[j].key) Console.Write(temp.child[j].key + " " ); } break ; } // Push the child nodes // of temp into the queue q.Enqueue(temp.child[i]); } } if (flag == 0) Console.Write( "No siblings!!" ); } static Node constructTree() { Node root = newNode(10); (root.child).Add(newNode(20)); (root.child).Add(newNode(30)); (root.child).Add(newNode(40)); (root.child[0].child).Add(newNode(50)); (root.child[0].child).Add(newNode(60)); (root.child[1].child).Add(newNode(70)); (root.child[1].child).Add(newNode(80)); (root.child[2].child).Add(newNode(90)); (root.child[2].child).Add(newNode(100)); (root.child[2].child).Add(newNode(110)); return root; } // Driver Code public static void Main(String[] args) { // Stores root of the // constructed tree Node root = constructTree(); int X = 30; // Print siblings of Node X Siblings(root, X); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for the above approach // Structure of a node of N-ary tree class Node { constructor(key) { this .child = []; this .key = key; } } // Function to create a // new node function newNode(key) { let temp = new Node(key); return temp; } // Function to find the // siblings of the node /// value function Siblings(root, value) { let flag = 0; if (root == null ) return ; // Stores nodes level wise let q = []; // Push the root q.push(root); // Continue until all // levels are traversed while (q.length > 0) { // Stores current node let temp = q[0]; q.shift(); // Enqueue all children // of the current node for (let i = 0; i < temp.child.length; i++) { // If node value is found if (temp.child[i].key == value) { flag = 1; // Print all children of current // node // except value as the answer for (let j = 0; j < temp.child.length; j++) { if (value != temp.child[j].key) document.write(temp.child[j].key + " " ); } break ; } // Push the child nodes // of temp into the queue q.push(temp.child[i]); } } if (flag == 0) document.write( "No siblings!!" ); } function constructTree() { let root = newNode(10); (root.child).push(newNode(20)); (root.child).push(newNode(30)); (root.child).push(newNode(40)); (root.child[0].child).push(newNode(50)); (root.child[0].child).push(newNode(60)); (root.child[1].child).push(newNode(70)); (root.child[1].child).push(newNode(80)); (root.child[2].child).push(newNode(90)); (root.child[2].child).push(newNode(100)); (root.child[2].child).push(newNode(110)); return root; } // Driver code // Stores root of the // constructed tree let root = constructTree(); let X = 30; // Print siblings of Node X Siblings(root, X); // This code is contributed by divyeshrabadiya07 </script> |
Output:
20 40
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us