how to find nodes of other subtrees?

[mnnsa]

I am trying to find all nodes that are not in subtree of a given node u.
There is an undirected tree that contains N nodes. the tree is rooted at node 1.
And N-1 space separated integers are given where i th value denoting the parent of (i+1)th node.

Input:
N u //N:number of nodes ,u: the node for which we have to find nodes excluding its subtree

a b c d // N-1 space separated integers are given where i th value denoting the parent of (i+1)th node.


ANY suggestions how to design dfs algo for this?

[ne555]

def traverse(root):
   if root == u:
      return;
   //print(root) //preorder
   for c in root.children:
      traverse(c)
   print(root) //postorder 

[mnnsa]

this will skip printing nodes if "u" is visted before other subtreees

[lastchance]

#include <iostream>
#include <sstream>
#include <vector>
using namespace std;


using Tree = vector< vector<int> >;


void traverse( const Tree &tree, int parent, int u )
{
   if ( parent != u )
   {
      cout << parent << " ";
      for ( int child : tree[parent] ) traverse( tree, child, u );
   }
}

int main()
{
   int N, u, parent;
   istringstream in( "11  3\n"
                     "1  1  1  2  2  2  3  3  3  4\n" );

   in >> N >> u;
   Tree tree(1+N);
   for ( int child = 2; child <= N; child++ )
   {
      in >> parent;
      tree[parent].push_back( child );
   }

   cout << "Nodes not in subtree of " << u << " are:\n";
   traverse( tree, 1, u );
}

For the following tree, and node u = 3:

             1
             |
   /---------+--------\
   |         |        |
   2         3        4
   |         |        |
/--+--\   /--+--\     |
|  |  |   |  |  |     |
5  6  7   8  9  10    11

Nodes not in subtree of 3 are:
1 2 5 6 7 4 11 

[mnnsa]

Thanks .

[Enoizat]

And N-1 space separated integers are given where i th value denoting the parent of (i+1)th node.

May I ask a question about English? When I read the above sentence, what I understand is that the subtree nodes values should ‘descend’ from their parent node; in that case, the structure should more or less be like so:

             1
             |
   /---------+---------\
   |         |         |
   2         6        10
   |         |         |
/--+--\   /--+--\   /--+--\
|  |  |   |  |  |   |  |  |
3  4  5   7  8  9  11 12 13

How should I interpret that sentence instead?

[lastchance]

I think it is as I have drawn it, @Enoizat.

The first value in that long line is the parent of node 2.
The second value is the parent of node 3.
The third value is the parent of node 4.
...
The 10th value is the parent of node 11.


So if the line giving the parents is
1 1 1 2 2 2 3 3 3 4
then nodes 2, 3 and 4 all have parent 1,
nodes 5, 6, 7 have parent 2,
nodes 8, 9, 10 have parent 3,
node 11 has parent 4.

The tree is then

             1
             |
   /---------+--------\
   |         |        |
   2         3        4
   |         |        |
/--+--\   /--+--\     |
|  |  |   |  |  |     |
5  6  7   8  9  10    11

as drawn earlier. I needed a somewhat asymmetric tree to test more values of u. I could have done with testing more levels, but the input file got longer and longer.

[Enoizat]

mnnsa wrote:

where i th value denoting the parent of (i+1)th node.

lastchance wrote:

The first value in that long line is the parent of node 2.
The second value is the parent of node 3.
The third value is the parent of node 4.
...

Thank you. That isn’t so easy to catch if you aren’t a native English speaker.
Maybe the original spoj-or-whatever instructions were less ambiguous.