title: How do I implement the OS-Rank() function for my binary tree in Python?
body: <p>I'm trying to implement the OS-Rank() function for my binary tree that I've built. OS-Rank tags a node with a count of smaller nodes from the tree, and stores it in node.size. This allows OS-Select to easily select the i'th smallest node in O(nlgn) time.</p>
  
  <p>Here is the pseudo code:</p>
  
  <pre><code>OS-RANK(x)
      r = x.left.size + 1
      y = x
      while y != T.root
          if y == y.parent.right
              r = r + y.parent.left.size + 1
          y = y.parent
      return r
  </code></pre>
  
  <p>Here's my code:</p>
  
  <pre><code>def osrank(self, root):
      r = 0
      if self.left != None:
          r = self.left.size + 1
      else:
          r += 1
      y = self
      while y != root:
          if y == y.parent.right:
              if y.parent.left != None:
                  r = r + y.parent.left.size + 1
              else:
                  r += 1
          y = y.parent
      self.size = r
  </code></pre>
  
  <p>Not too different, except that I had to handle cases where nodes were null.</p>
  
  <p>However, when I print out my in order traversal after inserting {5,2,7,1,6}, I get this:</p>
  
  <blockquote>
    <p>L L 1(1) U 2(1) U 5(1) R L 6(3) U 7(3) U U</p>
  </blockquote>
  
  <p>(L/U/R describes traversals, and the number in brackets is node.size, or the rank).
  I think I'm expecting something like this:</p>
  
  <blockquote>
    <p>L L 1(1) U 2(2) U 5(5) R L 6(1) U 7(2) U U</p>
  </blockquote>
  
  <p>Any advice?</p>