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.)

Answer rating: 100% (QA)

We need to define a data structure named Pair such that it contains two values first and second wher... View the full answer