A y-fast trie consists of two data structures: the top half is an x-fast trie and the lower half consists of a number of balanced binary trees.
Since the x-fast trie stores O(n / log M) representatives and each representative occurs in O(log M) hash tables, this part of the y-fast trie uses O(n) space.