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> |
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> |
5 100
Â
Time Complexity: O(N)Â
Auxiliary Space: O(N)Â
Â
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!


… [Trackback]
[…] Here you will find 57790 more Information to that Topic: geeksforgeeks.org/print-all-nodes-present-in-the-subtree-of-a-given-node-of-a-binary-tree/ […]
… [Trackback]
[…] Here you can find 23957 more Info on that Topic: geeksforgeeks.org/print-all-nodes-present-in-the-subtree-of-a-given-node-of-a-binary-tree/ […]
… [Trackback]
[…] Find More here on that Topic: geeksforgeeks.org/print-all-nodes-present-in-the-subtree-of-a-given-node-of-a-binary-tree/ […]
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/print-all-nodes-present-in-the-subtree-of-a-given-node-of-a-binary-tree/ […]