## Dynamic Programming – 6 : Optimum sum of tree nodes

February 3, 2011 Leave a comment

**Optimum sum of tree nodes **

We are given a rooted tree with root . Each node has a real value associated with it. We are to find a subset of nodes of the tree, such the sum of the values of the selected nodes is maximized, subject to the condition that if we choose a node , we cannot choose any of its children or its parent.

**Solution. **

**Notation. **Let denote the optimum value on a sub-tree rooted at node . Let denote the optimum value on a sub-tree rooted at node subject to the condition that is selected as part of the optimal subset. Let denote the optimum value on a sub-tree rooted at subject to the condition that is not selected as part of the optimal subset.

Then, we have that:

.

(where the summation is over all children of .)

(where the summation is over all children of .)

—

Also, if is a leaf, then , and .

**Pseudocode for computing OPT(root)**

We can compute OPT(root) in a bottom up fashion starting from the leaves. The recurrence equations for a node involve the OPT values for its children. Thus, before computing the value for node , we compute the values for its children.

Let the nodes of the tree be arranged in levels from Level 0 till Level L such that the root is at Level 0.

**For i going from L downto 0:**

**For all nodes x in Level i: **

**Compute OPT[1,x], OPT[0,x] and OPT[x] using the above recurrence. **

**Set Soln[x] = 1 if OPT[1,x] >= OPT [0,x]. Else, set Soln[x] = 0.
**

**End. **

**—-**

The above code has a running time of where represents the number of nodes in the tree. [ We compute OPT values for n nodes. For each node, we compute the OPT values by summing up the OPT values over all of its children. Aggregating over all nodes, and observing the each node can have at most one parent, we find that the summing up operation costs O(n). Therefore, the total cost is O(n+n) which is O(n). Another way to look at it is that the aggregate cost of the summing up operations over all nodes is O(m) [where m represents the number of edges in the tree], which for a tree is O(n). ]

—-

**Computing the optimal subset: **

We do so using the Soln[x] values.

**Function: Print_Solution (x) **

**If (Soln[x] == 1) **

**Print x.
**

**For all grand-children y of x: **

**Print_Solution (y); **

**Else**

**For all children y of x: **

**Print_Solution (y); **

**End. **

**—- **

Print_Solution(root) has a running time of .

—-