Rank of an element in a stream | Python3 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
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE self . leftSize = 0 NEW_LINE DEDENT DEDENT def insert ( root , data ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return newNode ( data ) NEW_LINE DEDENT if data <= root . data : NEW_LINE INDENT root . left = insert ( root . left , data ) NEW_LINE root . leftSize += 1 NEW_LINE DEDENT else : NEW_LINE INDENT root . right = insert ( root . right , data ) NEW_LINE DEDENT return root NEW_LINE DEDENT def getRank ( root , x ) : NEW_LINE INDENT if root . data == x : NEW_LINE INDENT return root . leftSize NEW_LINE DEDENT if x < root . data : NEW_LINE INDENT if root . left is None : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return getRank ( root . left , x ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if root . right is None : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT rightSize = getRank ( root . right , x ) NEW_LINE if rightSize == - 1 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return root . leftSize + 1 + rightSize NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 5 , 1 , 4 , 4 , 5 , 9 , 7 , 13 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE x = 4 NEW_LINE root = None NEW_LINE for i in range ( n ) : NEW_LINE INDENT root = insert ( root , arr [ i ] ) NEW_LINE DEDENT print ( " Rank ▁ of " , x , " in ▁ stream ▁ is : " , getRank ( root , x ) ) NEW_LINE x = 13 NEW_LINE print ( " Rank ▁ of " , x , " in ▁ stream ▁ is : " , getRank ( root , x ) ) NEW_LINE x = 8 NEW_LINE print ( " Rank ▁ of " , x , " in ▁ stream ▁ is : " , getRank ( root , x ) ) NEW_LINE DEDENT