CTCI-11.8

Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x).implement the data structure and algorithms to support these operations. That is, implement the method track(int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or eauql to x (not including x itself).

CTCI-11.8.java

class LookUpRankBST{
    Node root;
    
    static class Node{
        int value;
        int leftNodesNumber;
        Node left, right;
        Node(int v){
            this.value = v;
            this.leftNodesNumber = 0;
            this.left = null;
            this.right = null;
        }
    }
    
    public LookUpRankBST(){
        root = null;
    }
    
    public void insert(int input){
        root = insert(input, root);
    }
    
    private void insert(int input, Node root){
        if(root == null) return new Node(input);
        else if(input > root.value) root.right = insert(input, root.right);
        else if(input <= root.value){
            root.left = insert(input, root.left);
            root.leftNodesNumber++;
        }
        return root;
    }
    
    public int lookUpRank(int input){
        return lookUpRank(input, root);
    }
    
    private int lookUpRank(int input, Node root){
        if(root == null) return -1;
        else if(input == root.value) return root.leftNodesNumber;
        else if(input < root.value) return lookUpRank(input, root.left);
        else if(input > root.value){
            int rightResult = lookUpRank(input, root.right);
            if(rightResult == -1) return -1;
            return (rightResult + root.leftNodesNumber + 1);
        }
    } 
}