Binary Search Tree Code

A binary tree is either empty, or it consists of one vertex together with two trees linked to it. These two trees are called the left subtree and the right subtree. Each vertex holds one lowercase letter of the English alphabet. The vertex that is not a subtree of any other vertex is called the root.

A tree is a binary search tree (BST) if the following condition holds at every vertex: all letters in the left subtree precede, in alphabetical order, the letter at the root, and all letters in the right subtree follow the letter at the root.

The code of a BST is defined as follows.

• If the tree is empty, the code is the empty string (0 letters).
• Otherwise, it is the letter at the root, followed by the code of the left subtree, followed by the code of the right subtree.

Consider every BST that has $k$ vertices holding the first $k$ letters of the English alphabet. Write the codes of all such trees in alphabetical order. The $n$-th code in that list is called the $(n, k)$-code.

For example, there are exactly 14 BSTs with 4 vertices, and their codes in alphabetical order are:

abcd abdc acbd adbc adcb bacd badc cabd cbad dabc dacb dbac dcab dcba

The string badc is the $(7, 4)$-code, and it corresponds to the BST shown below.

Write a program that:

• reads the two integers $n$ and $k$ from standard input,
• finds the $(n, k)$-code, and
• writes it to standard output.

The first and only line of standard input contains two positive integers $n$ and $k$, separated by a single space, with $1 \le k \le 19$. The value $n$ is not greater than the total number of codes of BSTs with $k$ vertices.

The first and only line of standard output must contain exactly one word, written in lowercase letters, which is the $(n, k)$-code.