Sort and count duplicates X31308

Write a function count_dup that reads words, possibly including repeated ones, and writes them in sorted order, each together with its number of occurrences.

Input A sequence of nonempty words along possibly several lines, separated by spaces or end of line characters. Each word consists of arbitrary letters.

Output All the words appearing in the input, once each, in alphabetical order, and each followed by a colon, a space, and the number of times it appears in the input. See the example.

Observation You program must contain exactly one data structure, namely, a BST to be implemented by you. It can use also strings freely and, of course, nonstructured types like ints and bools. Other than that, ALL data structures are forbidden: no lists, no dicts, no Counters, no defaultdicts, no nothing.