Vidhya
BAN USER
Comments (2)
Reputation 5
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
My O(N) solution. But I am using extra O(N) space too.
class Tree{
List<Integer> children;
Tree(){
children = new ArrayList<Integer>();
}
}
public void cutSubTree(Node [] node , int ind){
int n = node.length;
Tree tree[] = new Tree[n];
for (int i=0; i<n; i++){
tree[i] = new Tree();
}
for (int i =0; i<n; i++){
if (node[i].pI != 1)
tree[node[i].pI].children.add(i);
}
printValids(node);
makeInvalid(tree, node, ind);
printValids(node);
}
public void makeInvalid(Tree[] tree, Node[] node, int ind){
node[ind].isValid = false;
for (int i: tree[ind].children)
makeInvalid(tree, node, i);
}
public void printValids(Node[] node){
for (int i =0; i<node.length; i++){
if (node[i].isValid){
System.out.print(node[i].node + " ");
}
}
System.out.println();
}

Vidhya
May 15, 2017 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
 Vidhya May 15, 2017