Number of nodes with value less than median values of all the nodes in subtree

Правка en1, от swordx, 2023-04-05 20:07:51

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский swordx 2023-04-05 20:07:51 934 Initial revision (published)