0
$\begingroup$

Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be included.

My intuition tells me dynamic programming (and possibly two-coloring) should be involved, but not sure where to start. Could you please offer me a hint?

$\endgroup$
  • $\begingroup$ See the answer here. $\endgroup$ – hengxin May 31 '15 at 11:40
1
$\begingroup$

This problem is known as Independent Set (and not two-coloring). Your intuition is quite correct though.

As a hint, I'd like to offer the following definitions:

Let $n$ be a node of the binary tree. Let $P(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may not be included. Similarly, let $Q(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may be included.

$\endgroup$
  • $\begingroup$ Thanks. Unfortunately my "reputation" does not allow me to upvote. $\endgroup$ – Vectorizer May 31 '15 at 15:29
  • $\begingroup$ Learnt quite a bit. Is there a way to modify the algorithm to identify the nodes participating in the maximum sum? $\endgroup$ – Vectorizer Jun 2 '15 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.