Clear order statistic (binary search) tree implementation


  • 0
    L

    The idea is the same as other posted BST solutions: view suffix of the array after position i as sorted, find ith element's rank within this suffix, and then have ith element join it to generate a new suffix.

    public class Solution {
      class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        int lcount;
        int size;
    
        TreeNode(int val) {
          this.val = val;
          size = 1;
        }
      }
    
      TreeNode insert(TreeNode root, int val) {
        if (root == null)
          return new TreeNode(val);
    
        root.size++; // for getting rank k element; not used in this problem
        if (val < root.val) {
          root.lcount++;
          root.left = insert(root.left, val);
        } else { // allows duplicate by having later ones on the right subtree
          root.right = insert(root.right, val);
        }
    
        return root;
      }
    
      int rank(TreeNode root, int val) {
        if (root == null) {
          return 1; // as if the previously non-existent val gets inserted here
        }
    
        if (val == root.val)
          return root.lcount + 1;
        else if (val < root.val) {
          return rank(root.left, val);
        } else {
          return rank(root.right, val) + root.lcount + 1;
        }
      }
    
      public List<Integer> countSmaller(int[] arr) {
        List<Integer> col = new ArrayList<>();
        TreeNode root = null;
        for (int i = arr.length - 1; i >= 0; i--) {
          col.add(rank(root, arr[i]) - 1);
          root = insert(root, arr[i]);
        }
    
        Collections.reverse(col);
        return col;
      }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.