If rules of creating BST is as follows:

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.

If a node has level i, then the subtree rooted at that node should have exactly 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.

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.

I read the editorial https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/algorithm/monk-and-bst/editorial/

It says that we can observe that, in subtree with N nodes, (N-1)/2 nodes will occur twice and 1 node will occur exactly once, which will be of maximum value, and tree will be of form: img

Can someone explain why is this so, or better yet point me to some resource which will help me understand this.

Note that the number of nodes in the

L-level BSTN(L) = 2^{L}- 1 is always an odd number, and thatN(L) = 2N(L- 1) + 1. It should be possible to derive an iterative algorithm that generates theL+ 1-levels min-sum BST from theL-levels min-sum BST as follows.Assume at first that the condition

S≥ 1 is relaxed, and thatS= 0. A 1-level min-sum BST is a root node with value 0. A 2-levels min-sum BST has a root node with value 1, and two 1-level BST subtrees; the left and right BST subtrees have root nodes with values 0 and 1, respectively.In general, the left

L-levels min-sum BST subtree should be identical to previousL-levels min-sum BST. To maintain the distinctiveness property of the node values in each subtree, theL-levels min-sum BST right subtree should be generated from theL-levels min-sum BST left subtree by adding 2^{L - 1}to the value of each node.The value of the root node of

L+ 1-levels min-sum BST should be equal to the maximum value in theL-levels min-sum BST left subtree. Such value which is equal toN(L- 1) appears only once in theL-levels subtree. After assigning such value to the root of the newly generatedL+ 1 min-sum BST, the value should appear exactly twice in the tree, and the new maximum value ofL+ 1 BST isN(L) which is the maximum value of theL-levels min-sum right subtree. Again, such value appears now exactly once, and the pattern repeats each timeLis incremented by 1. It should be possible to prove that the total sum of theL+ 1-levels min-sum BST can be expressed recursively asT(L+ 1) = 2T(L) +N(2L- 1), forL≥ 1where the base case is

T(1) = 0. To deal with the case whenS≥ 1, it is sufficient to generate the min-sum BST as stated before, and computeT(L) for it. IfT(L) is greater thanS, thenT(L) is the minimum possible sum. Otherwise, it is necessary to add a strictly positive integerd_{min}to each node such that the new total sum is greater thanS. Since the total number of nodesN(L) of the BST is known,d_{min}can be computed in constant time.A final note is that generating a full BST with about 100,000 nodes is usually possible for up to 16 levels. Most Memory Limits for competitive programming problems are often exceeded when

Lis increased above this number.