Help needed- Find number of nodes in n array tree whose value is more than the median of the subtree

1

Hi Everyone,

Could you help with a problem statement.

We have a n array tree with following structure:

struct Node {
  int value;
  vector<Node*> children;
}

We want to find the number of nodes in this tree whose value is lesser than the median of all the values in the subtree rooted at a given node.

Let me know if you need more clarification.

What could be the most optimal way to solve this problem?