All Tracks Data Structures Trees Binary Search Tree Problem

Monk and BST

Data Structures, Easy-Medium, Trees


Monk as always has brought a new task for Fredo. He asks Fredo to create a Binary Search Tree (BST) with L levels and \(2^L-1\) nodes. Let the sum of all node values in the BST be M. He further adds that M should be smallest possible integer greater than S, where S is an integer given by Monk. He states the rules of creating BST as follows:

  1. The left sub-tree contains only nodes with values less than or equal to the parent node; the right sub-tree contains only nodes with values greater than the parent node.
  2. If a node has level i, then the subtree rooted at that node should have exactly \(2^{L-i}\) number of distinct values in the subtree. Note that it is the number of distinct values in the subtree and not the number of nodes in the subtree.
  3. If a is the smallest value in the tree and b is the largest value, then all values from a to b must come atleast once in the tree.

Level of root is 1, next level is 2 and so on.

Now, he will ask two type of queries to Fredo.
Type 0: Find the closest node to root whose value is equal to \(val\) and print path to that node from the root. If root has value equal to \(val\), print "\(root\)". Else print "l" when we visit left child of any node and "r" when we visit right child of any node.
Type 1: Tell the value of \(k^{th}\) node in the tree. The nodes are numbered as:

enter image description here
Here 1,2 and so on are node numbers and A,B etc. are values of nodes.

Finally, he will ask Fredo Q queries, each query belonging to one of the types mentioned above. Since, Fredo is new to this concept, help him complete this task.

Input Format:
First line consists of two integers L and S as described in the question.
Second line consists of Q, denoting the number of queries.
Each of the following Q lines consists of two integers. The first integer denoting the \(type\) of query and second denoting either \(val\) or k as described in the queries.

Output Format:
For each query, print the required answer in a separate line.

Input Constraints:
\(1 \le L \le 30\)
\(1 \le S \le 10^{18}\)
\(1 \le Q \le 10^5\)
\(0 \le type \le 1\)
\(1 \le k \le 2^L-1\)
\(val\) is in between minimum and maximum value in tree(inclusive).
Values of S, \(val\) and k are such that answer would always exist for them.
Node values will be non-negative for all inputs.
M will never exceed \(2 \times 10^{18}\)

3 16
0 3
0 4
1 4
1 7
0 5

The tree would look like:

enter image description here

Sum = 3+2+4+2+3+4+5=23 which is smallest possible sum which we can get which is greater than 16.
Query 1: Node with value 3 which is closest to root is root itself.
Query 2: Node with value 4 which is closest to root is right child of root. So, we print "r".
Query 3: Value of node at number 4 is 2.
Query 4: Value of node at number 7 is 5.
Query 5: Node with value 5 which is closest to root is grandchild of root. So, we print "rr" which is path to node from root.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

CodeMonk (Trees)

View All Notifications