5
Number of nodes with value less than median values of all the nodes in subtree
source link: http://codeforces.com/blog/entry/114783
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK