Compute current rank of a node in a stream

node_rank.py

# Computing current rank of a node in a stream

class Node:
  def __init__(self, val, left=None, right=None, left_size=0):
    self.val = val
    self.left = left
    self.right = right
    self.left_size = left_size

class Solution:
  ''' Tip: Count number of nodes in the left for every parent node.'''
  def get_rank(self, node, val):
    rank = 0
    while node:
      if val < node.val: # move left
        node.left_size += 1
        if node.left is None:
          node.left = Node(val) 
          return rank
        else:
          node = node.left
      elif val > node.val: # move right
        rank += (1 + node.left_size)
        if node.right is None:
          node.right = Node(val)
          return rank
        else:
          node = node.right


if __name__=='__main__':
  from random import randint
  arr = [randint(0,2000) % randint(1,1991) for _ in range(10)]
  print("Given = {0}".format(arr))

  result = []

  val = arr.pop(0)
  root = Node(val)
  rank = 0
  result.append(1 + rank)

  s = Solution()

  for a in arr:
    result.append(1 + s.get_rank(root, a))

  print("Ranks = {0}".format(result))