What are competitive programming problems that require a tree data structure to solve them?
How about Huffman encodings?


  Given a text that uses an alphabet of $n$ unique characters, how can we uniquely encode the alphabet so that the text uses the smallest amount of bits?


More formally for Huffman encodings (as formulated by Tardos &amp; Kleinberg in their book Algorithm Design):


  Given an alphabet and a set of frequencies for letters, we would like to produce a prefix code that is as efficient as possible - namely, a prefix code that minimises the average number of bits per letters $ABL(\gamma) = \sum\limits_{x\in S} f_x|\gamma(x)|$. We will call such a prefix code optimal.


This has an $O(n \log n)$ solution.