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 non-empty, 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 pre-order code of a BST is a String obtained in the following way:
- The pre-order code of an empty BST is an empty string.
- The pre-order code of a non-empty BST is obtained in the following way: Let L and R be the pre-order codes of the left and right subtree, respectively. Then the pre-order code of the whole BST is the concatenation of the letter in its root node, L and R (in this order).
The pre-order 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 pre-order codes.
Our sequence of BSTs is one-based, i.e., the index of the first tree in this sequence is 1.
Return the pre-order 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.
|