I gave the max-heap based approach, in which I told him to insert every item into the max-heap, and then return the top K. For this, he asked the time Complexity, I answered O(Klog(K*N)). He told me to optimize it further. This time I gave a pointer based approach, i.e., to set a pointer at every category and then check for max among them, then increment count for the pointer of the category in...

For each node there can be four ways that the max path goes through the node:
1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child

The idea is to keep trace of four paths and pick up the max one in the end. An important thing to note is, root of every subtree need to retu...