A binary tree is either empty or it consists of a root node and two binary trees, called the left subtree and the right subtree of the root node. Each node of our binary trees will contain one lowercase letter. We say that a binary tree is a binary search tree (BST) if and only if for each node the following conditions hold:
 All letters in the left subtree of the node occur earlier in the alphabet than the letter in the node.
 All letters in the right subtree of the node occur later in the alphabet than the letter in the node.
Note that if a tree is a BST, then each subtree of this tree is also a BST. As a consequence, if the tree is nonempty, then both subtrees of the root node are BSTs again.
Examples of BSTs with 4 nodes:
c b a
/ \ / \ \
b d a d c
/ / / \
a c b d
A preorder code of a BST is a String obtained in the following way:
 The preorder code of an empty BST is an empty string.
 The preorder code of a nonempty BST is obtained in the following way: Let L and R be the preorder codes of the left and right subtree, respectively. Then the preorder code of the whole BST is the concatenation of the letter in its root node, L and R (in this order).
The preorder codes for the trees above are "cbad", "badc" and "acbd", respectively.
Consider all BSTs with exactly N nodes containing the first N lowercase letters. Order these trees alphabetically by their preorder codes.
Our sequence of BSTs is onebased, i.e., the index of the first tree in this sequence is 1.
Return the preorder code of the BST at the specified index in this sequence.
If index is larger than the number of BSTs with exactly N nodes, return an empty string.
