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, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

CodeMonk (Trees)

View All Notifications