# Binary tree node value maximization

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?

• See the answer here. May 31 '15 at 11:40

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.