Computing rank of a node in a binary search tree

Question

If each node in a binary search tree stores its weight (number of nodes in its subtree), what would be an efficient method to compute a rank of a given node (its index in the sorted list) as I search for it in the tree?

Oloughlin

Answer 1

Start the rank at zero. As the binary search proceeds down from the root, add the sizes of all the left subtrees that the search skips by, including the left subtree of the found node.

I.e., when the search goes left (from parent to left child), it discovers no new values less than the searched item, so the rank stays the same. When it goes right, the parent plus all the nodes in the left subtree are less than the searched item, so add one plus the left subtree size. When it finds the searched item. any items in the left subtree of the node containing the item are less than it, so add this to the rank.

Putting this all together:

int rank_of(NODE *tree, int val) {
  int rank = 0;
  while (tree) {
    if (val < tree->val) // move to left subtree
      tree = tree->left;
    else if (val > tree->val) {
      rank += 1 + size(tree->left);
      tree = tree->right;
    }
    else 
      return rank + size(tree->left);
  }
  return NOT_FOUND; // not found
}

This returns the zero-based rank. If you need 1-based then initialize rank to 1 instead of 0.

Importunity

This is brilliant ! – Voltmer

Your solution is simple and clean. I have tried solving this problem by maintaining all children count at every node. That was complex and prone to mistakes instead, it's a lot easier to just maintain the size of the left subtree as you did. Thanks! – Volauvent

Answer 2

Since each node has a field storing its weight, the first you should implement a method call size() which return the number of nodes in a node's substree:

private int size(Node x)
{
if (x == null) return 0;
else return x.N;
} 

then compute the rank of a given node is easy

public int rank(Node key)
{ return rank(key,root) }

    private int rank(Node key,Node root)
    {
        if root == null 
             return 0;
        int cmp = key.compareTo(root);
// key are smaller than root, then the rank in the whole tree
// is equal to the rank in the left subtree of the root.
        if (cmp < 0) {
            return rank(key, root.left) 
        } 
//key are bigger than root,the the rank in the whole tree is equal
// to the size of subtree of the root plus 1 (the root) plus the rank 
//in the right sub tree of the root.
        else if(cmp > 0){
            return size(root.left) + 1 + rank(key,root.right); 
        } 
// key equals to the root, the rank is the size of left subtree of the root
        else return size( root.left);  
    }

Chenab

The last else isn't correct. Only the left subtree of the root contains items less than the searched value. – Importunity

Answer 3

Depends on the BST implementation, but I believe you can solve it recursively.

public int rank(Key key){
    return rank(root, key);
}

private int rank(Node n, Key key){
    int count = 0;
    if (n == null)return 0;
    if (key.compareTo(n.key) > 0) count++;
    return count + rank(n.left, key) + rank(n.right, key);
}

Retrospect