Jan, Problem 1 | Promotion Counting

Promotion Counting

Problem Statement

Given a tree, for each node find the number of its children who’s value is greater than the original node’s value.

Intuition

If we iterate over the nodes with a DFS, we guarantee that we’ll visit all of the node’s children. Furthermore, we can guarantee that between entering and exiting a node, the only nodes processed are that node’s children.

More specifically, we maintain a BIT to keep track of our state. When we first visit a node, we sum from i - N. Then, we visit all of the node’s children. After visiting all of the children recursively, we again compute the sum of i - N. The difference is our answer. Finally, we update the BIT with our current node’s value and return.

Code

My solution can be found here

Written by Robert Chen

Notice any mistakes? Please email us at [email protected] so that we can fix any inaccuracies.