Connection Status:
Competition Arena > EncodingTrees

EncodingTrees

SRM 261 · 2005-08-30 · by misof

SRM 261 · 2005-08-30 · by misof · Recursion
Class Name: EncodingTrees
Return Type: String
Method Name: getCode
Arg Types: (int, int)
Problem Statement

Problem Statement

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.

Notes

  • You may assume that the number of our BSTs with 19 nodes doesn't exceed 2,000,000,000.

Constraints

  • N is between 1 and 19, inclusive.
  • index is between 1 and 2,000,000,000, inclusive.
Examples
0)
2
1
Returns: "ab"

There are 2 BSTs with 2 nodes. The first of them is a \ b

1)
2
2
Returns: "ba"

The second one is b / a

2)
2
3
Returns: ""

There are only 2 BSTs with 2 nodes, so the empty string is returned for an index of 3.

3)
4
9
Returns: "cbad"

The 14 valid pre-order codes of BSTs with 4 nodes: abcd, abdc, acbd, adbc, adcb, bacd, badc, cabd, cbad, dabc, dacb, dbac, dcab, dcba. The 9th tree: c / \ b d / a

4)
15
14023
Returns: "abcdeohgfniljkm"

Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EncodingTrees with a public method string getCode(int N, int index) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous