Could anyone share an optimal approach for solving the following question:

Given an n array tree, we need to find out the number of nodes whose value is less than the median value of all the nodes in the subtree for a given node.

You can assume the tree has structure like this:

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

Example:

In above example there are 3 such nodes where the value of the node is less than the median value of all nodes in its subtree.

Node-2 value is less than the median value that is 4(coming from Node-5).

Node-3 value is less than the median value that is 12(coming from Node-6).

Node-1 value is less than the median value that is 10(median of 2,4,10,12,22)

Let me know if the example is not clear.