Rank of an element in a stream | CPP program to find rank of an element in a stream . ; Inserting a new Node . ; Updating size of left subtree . ; Function to get Rank of a Node x . ; Step 1. ; Step 2. ; Step 3. ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; int leftSize ; } ; Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; temp -> leftSize = 0 ; return temp ; } Node * insert ( Node * & root , int data ) { if ( ! root ) return newNode ( data ) ; if ( data <= root -> data ) { root -> left = insert ( root -> left , data ) ; root -> leftSize ++ ; } else root -> right = insert ( root -> right , data ) ; return root ; } int getRank ( Node * root , int x ) { if ( root -> data == x ) return root -> leftSize ; if ( x < root -> data ) { if ( ! root -> left ) return -1 ; else return getRank ( root -> left , x ) ; } else { if ( ! root -> right ) return -1 ; else { int rightSize = getRank ( root -> right , x ) ; if ( rightSize == -1 ) return -1 ; return root -> leftSize + 1 + rightSize ; } } } int main ( ) { int arr [ ] = { 5 , 1 , 4 , 4 , 5 , 9 , 7 , 13 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int x = 4 ; Node * root = NULL ; for ( int i = 0 ; i < n ; i ++ ) root = insert ( root , arr [ i ] ) ; cout << " Rank ▁ of ▁ " << x << " ▁ in ▁ stream ▁ is : ▁ " << getRank ( root , x ) << endl ; x = 13 ; cout << " Rank ▁ of ▁ " << x << " ▁ in ▁ stream ▁ is : ▁ " << getRank ( root , x ) << endl ; x = 8 ; cout << " Rank ▁ of ▁ " << x << " ▁ in ▁ stream ▁ is : ▁ " << getRank ( root , x ) << endl ; return 0 ; }