Consider the following problem: You are given a pointer to the root r of a binary tree,
Question:
Consider the following problem: You are given a pointer to the root r of a binary tree, where each vertex v has pointers vie and v.rc to the left and right child, and a value Val(υ) > 0 . The value NIL represents a null pointer, showing that v has no child of that type. You wish to find the maximum total sum of vertices of a subset with the following constraints: If v is in the subset, then the following vertices cannot be in the subset:
• The parent of υ
• The children of υ
• The sibling of υ (the other vertex that shares the same parent as υ)
(you can assume that the tree is a full balanced binary tree with n vertices where n = 2 k — 1 for some k > 1.) (10 points for algorithm design.)(5 points for justification.)(5 points for runtime analysis.)