# Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes that are adjacent (means that for all v in Z, his parent and his childs are not in Z). A subgroup weight defined as the sum of the numbers of the included nodes in it.

Find an algorithm that finds an Isolated subgroup with the maximum weight.

I've tried to solve this question by set the root as the first node in the subgroup, then skip on his children and get the grandchild nodes.. something like that, but I don't find any greedy algorithm which can always take the nodes with the maximum number in it. I thought about to sort the tree in a way that the left child of a node is minimum and the right child is maximum, but what if a node have more than 2 childs?

• The complexity is proportional to the height or number of levels of a tree. Now, in worst case height of a tree is $O(n)$ and thus the complexity is $O(n)$, not $O(\log n)$ . May 14, 2014 at 14:39