0 votes

0

According to this link https://cs.stackexchange.com/questions/74163/what-is-rank-in-a-binary-search-tree-and-how-can-it-be-useful

shouldnt the rank of 50 be 5 since there are 5 keys that are smaller than 50?

0

so , in sorted list the node will be present after all of its left children , so count no of left children and add 1 that will be the position of the node(of which u want to find rank) in sorted list..

so here rank of 50 is 6

so here rank of 50 is 6

0

@lakshman use this algo u will get the rank of the node u want

```
int rank_of(NODE *tree, int val) {
int rank = 1;
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
}
```

0

@smoshree if u will go with zero based rank thn answer will be 7 bt if u will go with 1 based rank thne answer willl be 8 , we generally go with 1 based rank

0

Sort the list and you can easily find the rank.

10 |
20 |
30 |
40 |
45 |
50 |
55 |
60 |
65 |
70 |
75 |

** 1 2 3 4 5 6 7 8 9 10 11**

0

@lakshman we can do both it depends upon u which to take , check the program i have commented if u want indexing from 0 initialize rank =0 , bt generally we use 1 based rank

0

@dilip its not the case that we have to add one for rank ,

suppose u have started indexing from 0, then ( assuming the tree is right skew) rank of root is 0

suppose u have started indexing from 0, then ( assuming the tree is right skew) rank of root is 0

0

According to the question, It could be zero-based or 1-based Indexing.

https://stackoverflow.com/questions/26080924/computing-rank-of-a-node-in-a-binary-search-tree

http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/rbtrees.pdf