Ceiling in right side for every element in an array

http://massivealgorithms.blogspot.com/2015/12/leetcode-315-count-of-smaller-numbers.html
https://www.geeksforgeeks.org/ceiling-in-right-side-for-every-element-in-an-array/

Given an array of integers, find the closest greater element for every element. If there is no greater element then print -1

Examples:

Input : arr[] = {10, 5, 11, 10, 20, 12}
Output : 10 10 12 12 -1 -1

Input : arr[] = {50, 20, 200, 100, 30}
Output : 100 30 -1 -1 -1

A simple solution is to run two nested loops. We pick an outer element one by one. For every picked element, we traverse right side array and find closest greater or equal element. Time complexity of this solution is O(n*n)

A better solution is to use sorting. We sort all elements, then for every element, traverse toward right until we find a greater element (Note that there can be multiple occurrences of an element).

An efficient solution is to use Self Balancing BST (Implemented as set in C++ and TreeSet in Java). In a Self Balancing BST, we can do both insert and ceiling operations in O(Log n) time.

    public static void closestGreater(int[] arr)
    {
        int n = arr.length;
        TreeSet<Integer> ts = new TreeSet<Integer>();
        ArrayList<Integer> ceilings = new ArrayList<Integer>(n);
 
        // Find smallest greater or equal element
        // for every array element
        for (int i = n - 1; i >= 0; i--) {
            Integer greater = ts.ceiling(arr[i]);
            if (greater == null)
                ceilings.add(-1);
            else
                ceilings.add(greater);
            ts.add(arr[i]);
        }
 
        for (int i=n-1; i>=0; i--)
           System.out.print(ceilings.get(i) + " ");
    }

LeetCode 653 - Two Sum IV - Input is a BST

https://leetcode.com/problems/two-sum-iv-input-is-a-bst
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

X.
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106110/Java-Code-O(n)-time-O(lg(n))-space-using-DFS-%2B-Stack

The idea of using interator is from 173. Binary Search Tree Iterator. Since the in-order treversal of BST ouputs the value in ascending order, we can use iterator to get next smallest value in O(1) average time. Similarly, we can also implement a reverse iterator to get next largest value each time from BST. (For how to use stack to implement iterator, please refer to: https://discuss.leetcode.com/topic/6604/ideal-solution-using-stack-java)

With those two iterators in hand, now we can use two pointers to solve the problem.

Since the size iterator(stack) is the height of the BST tree, it only requries O(lg(n)) space.

So the overall performace is: O(n)/O(lg(n)).

    public boolean findTarget(TreeNode root, int k) {
        Stack<TreeNode> stackL = new Stack<TreeNode>();  // iterator 1 that gets next smallest value
        Stack<TreeNode> stackR = new Stack<TreeNode>();  // iterator 2 that gets next largest value
        
        for(TreeNode cur = root; cur != null; cur = cur.left)  
            stackL.push(cur);
        for(TreeNode cur = root; cur != null; cur = cur.right)  
            stackR.push(cur);
            
        while(stackL.size() != 0 && stackR.size() != 0 && stackL.peek() != stackR.peek()){
            int tmpSum = stackL.peek().val + stackR.peek().val;
            if(tmpSum == k)  return true;
            else if(tmpSum < k)
                for(TreeNode cur = stackL.pop().right; cur != null; cur = cur.left) 
                    stackL.push(cur);
            else
                for(TreeNode cur = stackR.pop().left; cur != null; cur = cur.right) 
                    stackR.push(cur);
        }
        
        return false;
    }

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106061/Java-Simple-AC-with-Time-O(n)-Space-O(log-n)-in-Average

Use the stack and search just like 2sum without dumping all the value out in the beginning.

-- Time/Space: n/logn in average

    public boolean findTarget(TreeNode root, int k) {
        if(root == null) return false;
     Stack<TreeNode> l_stack = new Stack<>();
     Stack<TreeNode> r_stack = new Stack<>();
     stackAdd(l_stack, root, true);
     stackAdd(r_stack, root, false);
     while(l_stack.peek() != r_stack.peek()){
         int n = l_stack.peek().val + r_stack.peek().val;
         if(n == k){
      return true;
         }else if(n > k){
      stackNext(r_stack, false);
         }else{
  stackNext(l_stack, true);
         }
     }
     return false;
    }
    
    private void stackAdd(Stack<TreeNode> stack, TreeNode node, boolean isLeft){
     while(node != null){
         stack.push(node);
            node = (isLeft) ? node.left : node.right;
     }
    }

    private void stackNext(Stack<TreeNode> stack, boolean isLeft){
     TreeNode node = stack.pop();
     if(isLeft){
         stackAdd(stack, node.right, isLeft);
     }else{
         stackAdd(stack, node.left, isLeft);
     }
    }

https://discuss.leetcode.com/topic/98440/java-c-three-simple-methods-choose-one-you-like

This method also works for those who are not BSTs. The idea is to use a hashtable to save the values of the nodes in the BST. Each time when we insert the value of a new node into the hashtable, we check if the hashtable contains k - node->val.

Time Complexity: O(n), Space Complexity: O(n).

    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<>();
        return dfs(root, set, k);
    }
    
    public boolean dfs(TreeNode root, HashSet<Integer> set, int k){
        if(root == null)return false;
        if(set.contains(k - root.val))return true;
        set.add(root.val);
        return dfs(root.left, set, k) || dfs(root.right, set, k);
    }

The idea is to use a sorted array to save the values of the nodes in the BST by using an inorder traversal. Then, we use two pointers which begins from the start and end of the array to find where there is a sum k.

Time Complexity: O(n), Space Complexity: O(n).

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> nums = new ArrayList<>();
        inorder(root, nums);
        for(int i = 0, j = nums.size()-1; i<j;){
            if(nums.get(i) + nums.get(j) == k)return true;
            if(nums.get(i) + nums.get(j) < k)i++;
            else j--;
        }
        return false;
    }
    
    public void inorder(TreeNode root, List<Integer> nums){
        if(root == null)return;
        inorder(root.left, nums);
        nums.add(root.val);
        inorder(root.right, nums);
    }

The idea is to use binary search method. For each node, we check if k - node->val exists in this BST.

Time Complexity: O(nlogn), Space Complexity: O(h). h is the height of the tree, which is logn at best case, and n at worst case.

    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root,  k);
    }
    
    public boolean dfs(TreeNode root,  TreeNode cur, int k){
        if(cur == null)return false;
        return search(root, cur, k - cur.val) || dfs(root, cur.left, k) || dfs(root, cur.right, k);
    }
    
    public boolean search(TreeNode root, TreeNode cur, int value){
        if(root == null)return false;
        return (root.val == value) && (root != cur) 
            || (root.val < value) && search(root.right, cur, value) 
                || (root.val > value) && search(root.left, cur, value);
    }

X. https://leetcode.com/articles/two-sum-iv/

  public boolean findTarget(TreeNode root, int k) {

    Set<Integer> set = new HashSet();

    Queue<TreeNode> queue = new LinkedList();

    queue.add(root);

    while (!queue.isEmpty()) {

      if (queue.peek() != null) {

        TreeNode node = queue.remove();

        if (set.contains(k - node.val))

          return true;

        set.add(node.val);

        queue.add(node.right);

        queue.add(node.left);

      } else

        queue.remove();

    }

    return false;

  }

Randomized Binary Search Trees

https://kukuruku.co/post/randomized-binary-search-trees/

int getsize(node* p) // a wrapper for size field. It operates with empty trees (t=NULL)
{
    if( !p ) return 0; 
    return p->size; 
}
void fixsize(node* p) //setting up a proper size of the tree 
{
    p->size = getsize(p->left)+getsize(p->right)+1; 
}

Inserting in a Tree Root

Application of a special insertion of a new key is the essential component of randomization. As a result of insertion, the new key is in the tree root. This information is useful in many ways, as the access to recently added keys is really fast, hello to self-organizing lists. To carry out the insertion in the root, we are going to need the rotate function that performs a local transformation of the tree.

Do not forget to update the size of subtrees and return a new tree root.

node* rotateright(node* p) // right rotation round p node 
{
    node* q = p->left; 
    if( !q ) return p; 
    p->left = q->right; 
    q->right = p; 
    q->size = p->size; 
    fixsize(p); 
    return q; 
}

node* rotateleft(node* q) // left rotation round q node 
{
    node* p = q->right;
    if( !p ) return q;
    q->right = p->left;
    p->left = q;
    p->size = q->size;
    fixsize(q);
    return p;
}

Now, let’s perform the insertion in the root. First of all, insert recursively a new key in the root of the left or the right subtrees (depending on the result of comparing with the root key) and perform a right (left) rotation that raises the necessary node to the tree root.

node* insertroot(node* p, int k) // inserting a new node with k key in p tree
{
    if( !p ) return new node(k); 
    if( k<p->key ) 
    {
        p->left = insertroot(p->left,k); 
        return rotateright(p); 
    }
    else 
    {
        p->right = insertroot(p->right,k);
        return rotateleft(p);
    }
}

Randomized Insertion

We have finally made it to randomization. At the moment, we have two insertion functions – a simple one and the one in the root. Let’s make a randomized insertion from them. It is known that if we mix all the keys beforehand and build a tree from them (the keys are inserted according to a standard scheme in order that has been achieved after hashing), the built tree will be quite balanced (its height will be around 2log2n compared to log2n for a perfectly balanced tree). Please note, that in this case any of source keys can be a root. But what should we do, if we do not know beforehand, what keys we will have (for instance, they’re introduced into system during a tree usage). But all of that is actually simple. Since any key (including the one we will insert in the tree now) can be a root with 1/(n+1) probability (n is the tree size before insertion), we execute the insertion with the given probability and a recursive insertion in the right or the left subtree (depending on the key value in the root) with 1-1/(n+1) probability.

node* insert(node* p, int k) // a randomized insertion of a new node with k key in p tree 
{
    if( !p ) return new node(k); 
    if( rand()%(p->size+1)==0 ) 
        return insertroot(p,k); 
    if( p->key>k ) 
        p->left = insert(p->left,k); 
    else
        p->right = insert(p->right,k); 
    fixsize(p); 
    return p; 
}


Key Deletion

So, we have an imbalanced (at least in some way) tree. As for now, it does not support key deletion. That’s exactly what we are going to solve now. The described in manuals variant operates fast, but does not really look nice (in contrast to insertion). We will follow a different path. Before deleting nodes, we will learn how to join trees together. Let there be given two trees with p and q roots. Any key of the first tree is less than any key of the second tree. It is required to join these two trees into a single one. We can accept any of two roots as the root of a new tree, let it be p. In this case, we can leave the left p subtree as it is and fix the join of two trees to p on the right – the right p subtree and the whole q tree (they meet all the requirements).



On the other hand, we can just as well make q node the root of a new tree. In the randomized implementation, we choose between these two alternatives in a random manner. Assume that the size of the left tree is n, while the right tree size is m. Then p is chosen to be a new root with n/(n+m) and q is chosen with m/(n+m) probability.
node* join(node* p, node* q) // joining two trees
{
    if( !p ) return q;
    if( !q ) return p;
    if( rand()%(p->size+q->size) < p->size ) 
    {
        p->right = join(p->right,q); 
        fixsize(p); 
        return p; 
    }
    else 
    {
        q->left = join(p,q->left); 
        fixsize(q); 
        return q; 
    }
}




Now everything is ready for deletion. We are going to delete by the key. Look for the node with the specified key (reminding you that all keys are different) and delete this node from the tree. The search stage is the same as searching. Then we join the right and the left subtrees of the found node, delete the node and return the root of the joined tree.
node* remove(node* p, int k) // deleting from p tree the first found node with k key 
{
    if( !p ) return p; 
    if( p->key==k ) 
    {
        node* q = join(p->left,p->right); 
        delete p; 
        return q; 
    }
    else if( k<p->key ) 
        p->left = remove(p->left,k); 
    else 
        p->right = remove(p->right,k); 
    return p; 
}

Implementation simplicity and beauty are the doubtless advantages of Binary Search Trees. But what’s the drawback? What do we pay for it? First of all, the additional memory for storing subtrees sizes. One integer-valued field per each node. As for Red-Black Trees, we can do without additional fields. On the other hand, the tree size information is not useless, since it allows to organize the access to the data by number (sampling or order statistics search), which transforms our tree into an ordered array with feasible insertion and deletion of any elements. Secondly, though the operation time is logarithmic, the proportionality coefficient will not be small as all the operations are performed in two passes (up and down). Besides, insertion and deletion require random numbers. But there’s also the good news. At the search stage everything should operate really fast. Finally, logarithmic time is not guaranteed. There’s always a chance that a tree will be ill-balanced. But when there are ten thousand of nodes, such possibility is so negligible that it’s worth risking.

http://algo.inria.fr/seminars/sem96-97/martinez.html

LeetCode 530 - Minimum Absolute Difference in BST

https://leetcode.com/problems/minimum-absolute-difference-in-bst

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

X. Inorder travsere
https://discuss.leetcode.com/topic/80796/java-o-n-time-inorder-traversal-solution

Since this is a BST, the inorder traversal of its nodes results in a sorted list of values. Thus, the minimum absolute difference must occur in any adjacently traversed nodes. I use the global variable "prev" to keep track of each node's inorder predecessor.

    int minDiff = Integer.MAX_VALUE;
    TreeNode prev;
    
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return minDiff;
    }
    
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null) minDiff = Math.min(minDiff, root.val - prev.val);
        prev = root;
        inorder(root.right);
    }

Indeed, hijacking a mutable array to emulate pass-by-reference reeks of a recovering C++ programmer (guilty as charged ;) )

class WrapInt{
    int value;
}

    public int getMinimumDifference(TreeNode root) {
     List<Integer> prev = new ArrayList<>(); // contains at most 1 value
     int[] min = new int[]{Integer.MAX_VALUE};
     inorder(root, prev, min);
     return min[0];
    }
    
    private void inorder(TreeNode root, List<Integer> prev, int[] min) {
     if (root == null) return;
     
     inorder(root.left, prev, min);
     if (prev.isEmpty()) {
      prev.add(root.val);
     } else {
      min[0] = Math.min(min[0], Math.abs(root.val - prev.get(0)));
      prev.set(0, root.val);
     }
     inorder(root.right, prev, min);     
    }

https://discuss.leetcode.com/topic/80823/twof-solutions-in-order-traversal-and-a-more-general-way-using-treeset

Solution 1 - In-Order traverse, time complexity O(N), space complexity O(1).

Could you explain using Integer.MAX_VALUE;

int min = Integer.MAX_VALUE;

That's just for initializing the return value. Because when you call

min = Math.min(min, Math.abs(root.val - set.floor(root.val)));

the first time, you want min to be whatever the right part is, which can be achieved by setting min to have the maximum possible value.

public class Solution {
    int min = Integer.MAX_VALUE;//
    Integer prev = null;
    
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        
        getMinimumDifference(root.left);
        
        if (prev != null) {
            min = Math.min(min, root.val - prev);
        }
        prev = root.val;
        
        getMinimumDifference(root.right);
        
        return min;
    }
    
}

What if it is not a BST? (Follow up of the problem) The idea is to put values in a TreeSet and then every time we can use O(lgN) time to lookup for the nearest values.

Solution 2 - Pre-Order traverse, time complexity O(NlgN), space complexity O(N).

    TreeSet<Integer> set = new TreeSet<>();
    int min = Integer.MAX_VALUE;
    
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        
        if (!set.isEmpty()) {
            if (set.floor(root.val) != null) {
                min = Math.min(min, Math.abs(root.val - set.floor(root.val)));
            }
            if (set.ceiling(root.val) != null) {
                min = Math.min(min, Math.abs(root.val - set.ceiling(root.val)));
            }
        }
        
        set.add(root.val);
        
        getMinimumDifference(root.left);
        getMinimumDifference(root.right);
        
        return min;
    }

中序遍历BST得到的序列是有序序列。因此创建一个vector存储中序遍历的每一个节点就得到一个有序序列，然后遍历这个有序序列，在遍历过程中求出两两之差并更新最小的绝对值之差就能得到结果。
http://www.liuchuo.net/archives/3714

    int getMinimumDifference(TreeNode* root) {

        inOrder(root);

        int result = INT_MAX;

        for (int i = 1; i < tree.size(); i++)

            result = min(result, tree[i] - tree[i-1]);

        return result;

    }

private:

    vector<int> tree;

    void inOrder(TreeNode* root) {

        if (root->left != NULL) inOrder(root->left);

        tree.push_back(root->val);

        if (root->right != NULL) inOrder(root->right);

    }

};

X. [lower, upper bound]
https://discuss.leetcode.com/topic/80916/java-no-in-order-traverse-solution-just-pass-upper-bound-and-lower-bound

It is just sort of property of the BST. Since the value of all the nodes of the left subtree is smaller than the current node, the value of the current node is the upper bound of the all the nodes in the left subtree. And for the right subtree, the value of the current node is the lower bound. You can draw a BST and have a look. If you draw a vertical line for 2 nodes, you will find all the nodes between those two lines are bounded by the value of the nodes which you draw the vertical lines.

Make use of the property of BST that value of nodes is bounded by their "previous" and "next" node.
Edit: Thanks to Stefan pointing out a small bug. Previous code would fail when testing [2147483647, 2147483646].
Now Long.MAX_VALUE/MIN_VALUE is used to mark the INF.

long minDiff = Long.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
    helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
    return (int)minDiff;
}
private void helper(TreeNode curr, long lb, long rb){
    if(curr==null) return;
    if(lb!=Long.MIN_VALUE){
        minDiff = Math.min(minDiff,curr.val - lb);
    }
    if(rb!=Long.MAX_VALUE){
    minDiff = Math.min(minDiff,rb - curr.val);
    }
    helper(curr.left,lb,curr.val);
    helper(curr.right,curr.val,rb);
}

def getMinimumDifference(self, root):
    def mindiff(root, lo, hi):
        if not root:
            return float('inf')
        return min(root.val - lo,
                   hi - root.val,
                   mindiff(root.left, lo, root.val),
                   mindiff(root.right, root.val, hi))
    return mindiff(root, float('-inf'), float('inf'))

X.
https://leetcode.com/problems/minimum-absolute-difference-in-bst/discuss/99905/Two-Solutions-in-order-traversal-and-a-more-general-way-using-TreeSet

What if it is not a BST? (Follow up of the problem) The idea is to put values in a TreeSet and then every time we can use O(lgN) time to lookup for the nearest values.

Solution 2 - Pre-Order traverse, time complexity O(NlgN), space complexity O(N).

public class Solution {
    TreeSet<Integer> set = new TreeSet<>();
    int min = Integer.MAX_VALUE;
    
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        
        if (!set.isEmpty()) {
            if (set.floor(root.val) != null) {
                min = Math.min(min, root.val - set.floor(root.val));
            }
            if (set.ceiling(root.val) != null) {
                min = Math.min(min, set.ceiling(root.val) - root.val);
            }
        }
        
        set.add(root.val);
        
        getMinimumDifference(root.left);
        getMinimumDifference(root.right);
        
        return min;
    }
}