Given two arrays Node_ID[] and Parent_ID[]., construct a binary tree where value of ith node is equal to Node_ID[i] and parent of ith node is Parent_ID[i]. Given a node X, the task is to print node values of the tree rooted at X.
Examples:
Input: Node_ID[]= [11, 48, 100, 5], Parent_ID[] = [48, 0, 5, 48], X = 5
Output: [5, 100]
Explanation:
The tree constructed is as follows:
48
/ \
11 5
/
100
Therefore, subtree of the node 5 contains the nodes {5, 100}.Input: Node_ID[] = [1, 2, 3], Parent_ID[] = [0, 1, 1], X = 2
Output: [2]
Naive Approach: Follow the steps below to solve the problem
- Construct a tree structure from Node_ID[] and Parent_ID[]
- Store the nodes with parent X in vector tree
- For each node, check if X is an ancestor of that node
- If found to be true, store the node in vector tree. Otherwise, continue.
- Print the nodes present in vector tree
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to print nodes// in the tree rooted at xvoid subtreeX(vector<int>& nid, vector<int>& pid, int x){ unordered_map<int, int> parent; vector<int> tree; // Map every node to its parent for (int i = 0; i < nid.size(); i++) { parent[nid[i]] = pid[i]; } // Subtree with x as root tree.push_back(x); for (int i = 0; i < nid.size(); i++) { int k = nid[i]; int p = k; // Iterate until k becomes // equal to the root while (k != 0) { if (parent[k] == x) { // x is an ancestor of nid[i] tree.push_back(nid[i]); break; } k = parent[k]; } } // Print elements in the subtree for (int node : tree) cout << node << " ";}// Driver Codeint main(){ vector<int> nid = { 11, 48, 100, 5 }; vector<int> pid = { 48, 0, 5, 48 }; int x = 5; // Function call to print nodes // in the tree rooted at x subtreeX(nid, pid, x); return 0;} |
Java
import java.util.*;class GFG { // Function to print nodes // in the tree rooted at x static void subtreeX(int[] nid, int[] pid, int x) { HashMap<Integer, Integer> parent = new HashMap<Integer, Integer>(); List<Integer> tree = new LinkedList<>(); // Map every node to its parent for (int i = 0; i < nid.length; i++) { parent.put(nid[i], pid[i]); } // Subtree with x as root tree.add(x); for (int i = 0; i < nid.length; i++) { int k = nid[i]; int p = k; // Iterate until k becomes // equal to the root while (k != 0) { if (parent.containsKey(k) && parent.get(k) == x) { // x is an ancestor of nid[i] tree.add(nid[i]); break; } k = parent.containsKey(k) ? parent.get(k) : -1; } } // Print elements in the subtree for (int node : tree) System.out.print(node + " "); } // Driver Code public static void main(String[] args) { int[] nid = { 11, 48, 100, 5 }; int[] pid = { 48, 0, 5, 48 }; int x = 5; // Function call to print nodes // in the tree rooted at x subtreeX(nid, pid, x); }}// This code is contributed by 29AjayKumar |
Python3
# Function to print nodes# in the tree rooted at xdef subtreeX(nid, pid, x): parent = {} tree = [] # Map every node to its parent for i in range(len(nid)): parent[nid[i]] = pid[i] # Subtree with x as root tree.append(x) for i in range(len(nid)): k = nid[i] p = k # Iterate until k becomes # equal to the root while (k != 0): if (parent[k] == x): # x is an ancestor of nid[i] tree.append(nid[i]) break k = parent[k] # Print elements in the subtree for node in tree: print(node, end = " ")# Driver Codeif __name__ == '__main__': nid = [11, 48, 100, 5] pid = [48, 0, 5, 48 ] x = 5 # Function call to print nodes # in the tree rooted at x subtreeX(nid, pid, x) # This code is contributed by mohit kumar 29. |
C#
using System;using System.Collections.Generic;public class GFG { // Function to print nodes // in the tree rooted at x static void subtreeX(int[] nid, int[] pid, int x) { Dictionary<int, int> parent = new Dictionary<int, int>(); List<int> tree = new List<int>(); // Map every node to its parent for (int i = 0; i < nid.Length; i++) { parent.Add(nid[i], pid[i]); } // Subtree with x as root tree.Add(x); for (int i = 0; i < nid.Length; i++) { int k = nid[i]; int p = k; // Iterate until k becomes // equal to the root while (k != 0) { if (parent.ContainsKey(k) && parent[k] == x) { // x is an ancestor of nid[i] tree.Add(nid[i]); break; } k = parent.ContainsKey(k) ? parent[k] : -1; } } // Print elements in the subtree foreach (int node in tree) Console.Write(node + " "); } // Driver Code public static void Main(String[] args) { int[] nid = { 11, 48, 100, 5 }; int[] pid = { 48, 0, 5, 48 }; int x = 5; // Function call to print nodes // in the tree rooted at x subtreeX(nid, pid, x); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Function to print nodes// in the tree rooted at xfunction subtreeX(nid, pid, x) { var parent = new Map(); var tree = []; // Map every node to its parent for (var i = 0; i < nid.length; i++) { parent.set(nid[i], pid[i]); } // Subtree with x as root tree.push(x); for (var i = 0; i < nid.length; i++) { var k = nid[i]; var p = k; // Iterate until k becomes // equal to the root while (k != 0) { if (parent.has(k) && parent.get(k) == x) { // x is an ancestor of nid[i] tree.push(nid[i]); break; } k = parent.has(k) ? parent.get(k) : -1; } } // Print elements in the subtree for(var node of tree) document.write(node + " ");}// Driver Codevar nid = [11, 48, 100, 5];var pid = [48, 0, 5, 48];var x = 5;// Function call to print nodes// in the tree rooted at xsubtreeX(nid, pid, x);</script> |
Output:
5 100
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach : Follow the steps below to optimize the above approach:
- Construct a tree structure from Node_ID[] and Parent_ID[]
- Perform DFS from node X.
- Store the nodes in a vector tree
- Print the nodes present in the vector tree
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// DFS to traverse subtree rooted at xvoid dfs(int x, vector<int>& tree, map<int, vector<int> >& child){ // Push x into the vector tree.push_back(x); // Check if x is a leaf node if (child.find(x) != child.end()) { // Recursively call dfs // for children of x for (int next : child[x]) { dfs(next, tree, child); } }}// Function to print nodes// in the tree rooted at xvoid SubtreeX(vector<int>& nid, vector<int>& pid, int x){ int n = nid.size(); map<int, vector<int> > child; // adding edges in a tree for (int i = 0; i < n; i++) { if (child.find(pid[i]) == child.end()) { // Initialize adjacency list child[pid[i]] = vector<int>(); } child[pid[i]].push_back(nid[i]); } // Stores nodes in the subtree vector<int> tree; // Perform DFS from node x dfs(x, tree, child); for (int node : tree) { cout << node << " "; }}// Driver Codeint main(){ vector<int> nid = { 11, 48, 100, 5 }; vector<int> pid = { 48, 0, 5, 48 }; int x = 5; // Function call to print nodes // in the tree rooted at x SubtreeX(nid, pid, x); return 0;} |
Java
import java.io.*;import java.util.*;class GFG{ // DFS to traverse subtree rooted at xstatic void dfs(int x, Vector<Integer> tree, Map<Integer, Vector<Integer>> child){ // Push x into the vector tree.add(x); // Check if x is a leaf node if (child.containsKey(x)) { // Recursively call dfs // for children of x for(int next : child.get(x)) { dfs(next, tree, child); } }} // Function to print nodes// in the tree rooted at xstatic void SubtreeX(Vector<Integer> nid, Vector<Integer> pid, int x){ int n = nid.size(); Map<Integer, Vector<Integer>> child = new HashMap<>(); // Adding edges in a tree for(int i = 0; i < n; i++) { if (!child.containsKey(pid.get(i))) { // Initialize adjacency list child.put(pid.get(i), new Vector<Integer>()); } child.get(pid.get(i)).add(nid.get(i)); } // Stores nodes in the subtree Vector<Integer> tree = new Vector<Integer>(); // Perform DFS from node x dfs(x, tree, child); for(int node : tree) { System.out.print(node + " "); }} // Driver Codepublic static void main (String[] args){ Vector<Integer> nid = new Vector<Integer>( Arrays.asList(11, 48, 100, 5)); Vector<Integer> pid = new Vector<Integer>( Arrays.asList(48, 0, 5, 48)); int x = 5; // Function call to print nodes // in the tree rooted at x SubtreeX(nid, pid, x);}}// This code is contributed by rag2127 |
Python3
# DFS to traverse subtree rooted at xdef dfs(x, tree, child): # Push x into the vector tree.append(x) # Check if x is a leaf node if x in child: # Recursively call dfs # for children of x for nextt in child[x]: dfs(nextt, tree, child)# Function to print nodes# in the tree rooted at xdef SubtreeX(nid,pid,x): n = len(nid) child = {} # Adding edges in a tree for i in range(n): if pid[i] not in child: # Initialize adjacency list child[pid[i]] = [] child[pid[i]].append(nid[i]) # Stores nodes in the subtree tree = [] # Perform DFS from node x dfs(x, tree, child) print(*tree) # Driver Codenid = [11, 48, 100, 5]pid = [48, 0, 5, 48]x = 5# Function call to print nodes# in the tree rooted at xSubtreeX(nid, pid, x)# This code is contributed by avanitrachhadiya2155 |
C#
using System;using System.Collections.Generic;class GFG { // DFS to traverse subtree rooted at x static void dfs(int x, List<int> tree, Dictionary<int, List<int>> child) { // Push x into the vector tree.Add(x); // Check if x is a leaf node if (child.ContainsKey(x)) { // Recursively call dfs // for children of x foreach(int next in child[x]) { dfs(next, tree, child); } } } // Function to print nodes // in the tree rooted at x static void SubtreeX(List<int> nid, List<int> pid, int x) { int n = nid.Count; Dictionary<int, List<int>> child = new Dictionary<int, List<int>>(); // Adding edges in a tree for(int i = 0; i < n; i++) { if (!child.ContainsKey(pid[i])) { // Initialize adjacency list child[pid[i]] = new List<int>(); } child[pid[i]].Add(nid[i]); } // Stores nodes in the subtree List<int> tree = new List<int>(); // Perform DFS from node x dfs(x, tree, child); foreach(int node in tree) { Console.Write(node + " "); } } // Driver code static void Main() { List<int> nid = new List<int>{11, 48, 100, 5}; List<int> pid = new List<int>{48, 0, 5, 48}; int x = 5; // Function call to print nodes // in the tree rooted at x SubtreeX(nid, pid, x); }}// This code is contributed by decode2207. |
Javascript
<script>// DFS to traverse subtree rooted at xfunction dfs(x,tree,child){ // Push x into the vector tree.push(x); // Check if x is a leaf node if (child.has(x)) { // Recursively call dfs // for children of x for(let next=0;next< child.get(x).length;next++) { dfs(child.get(x)[next], tree, child); } }}// Function to print nodes// in the tree rooted at xfunction SubtreeX(nid,pid,x){ let n = nid.length; let child = new Map(); // Adding edges in a tree for(let i = 0; i < n; i++) { if (!child.has(pid[i])) { // Initialize adjacency list child.set(pid[i], []); } child.get(pid[i]).push(nid[i]); } // Stores nodes in the subtree let tree = []; // Perform DFS from node x dfs(x, tree, child); for(let node=0;node< tree.length;node++) { document.write(tree[node] + " "); }}// Driver Codelet nid = [11, 48, 100, 5];let pid = [48, 0, 5, 48];let x = 5;// Function call to print nodes// in the tree rooted at xSubtreeX(nid, pid, x);// This code is contributed by unknown2108</script> |
Output:
5 100
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
