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 BST N(L) = 2L - 1 is always an odd number, and that N(L) = 2N(L - 1) + 1. It should be possible to derive an iterative algorithm that generates the L + 1-levels min-sum BST from the L-levels min-sum BST as follows.
Assume at first that the condition S ≥ 1 is relaxed, and that S = 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 previous L-levels min-sum BST. To maintain the distinctiveness property of the node values in each subtree, the L-levels min-sum BST right subtree should be generated from the L-levels min-sum BST left subtree by adding 2L - 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 the L-levels min-sum BST left subtree. Such value which is equal to N(L - 1) appears only once in the L-levels subtree. After assigning such value to the root of the newly generated L + 1 min-sum BST, the value should appear exactly twice in the tree, and the new maximum value of L + 1 BST is N(L) which is the maximum value of the L-levels min-sum right subtree. Again, such value appears now exactly once, and the pattern repeats each time L is incremented by 1. It should be possible to prove that the total sum of the L + 1-levels min-sum BST can be expressed recursively as
T(L + 1) = 2T(L) + N(2L - 1), for L ≥ 1
where the base case is T(1) = 0. To deal with the case when S ≥ 1, it is sufficient to generate the min-sum BST as stated before, and compute T(L) for it. If T(L) is greater than S, then T(L) is the minimum possible sum. Otherwise, it is necessary to add a strictly positive integer dmin to each node such that the new total sum is greater than S. Since the total number of nodes N(L) of the BST is known, dmin 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 L is increased above this number.