title: Finding the rank in a red-black tree without using a parent pointer
body: <p>I was given code for a red-black tree in class. The struct used to create a node does not have a parent pointer. I have most of my project working, but I cannot figure out how to compute the rank in O(lg n) time. By rank, I mean if you were to do an inorder-traversal and save the keys to an array starting at index 1, what index the given key would be stored. Doing this would be in O(n) time though which is not allowed.</p>
  
  <p>Reading through CLRS, the chapter Augmenting Data Structures has code to return the rank given the key. This is exactly what I need, but the problem is the code uses a parent pointer. Since we never used parent pointers in any of our red-black tree examples and this code does not include a parent pointer, I don't believe we are to change the entire given code just to get the rank to work, which leads me to believe there is a way to do it without using a parent pointer.</p>
  
  <p>The (fields?) that exist in the node struct are: a key (int), a pointer to the left child, pointer to the right child, sub-tree size (int), and the color (int).</p>
  
  <p>All code is done in C. What I am looking for is if this is possible, and how I might accomplish this with or without source code (a good explanation would be perfect).</p>