0 votes 0 votes Consider the following What is the rank(index) of the node $50?$ DS data-structures test-series + – Lakshman Bhaiya asked Nov 6, 2018 Lakshman Bhaiya 953 views answer comment Share Follow See all 22 Comments See all 22 22 Comments reply Naveen Kumar 3 commented Nov 6, 2018 reply Follow Share Is it 6? 0 votes 0 votes Lakshman Bhaiya commented Nov 6, 2018 reply Follow Share how can you explain, I never heard about the rank of the index? 0 votes 0 votes Naveen Kumar 3 commented Nov 6, 2018 reply Follow Share I found it here pls check & varify. 0 votes 0 votes Lakshman Bhaiya commented Nov 6, 2018 reply Follow Share thanks 0 votes 0 votes Somoshree Datta 5 commented Nov 17, 2018 reply Follow Share 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 votes 0 votes Lakshman Bhaiya commented Nov 17, 2018 reply Follow Share answer is $6$ 0 votes 0 votes Manas Mishra commented Nov 17, 2018 reply Follow Share Rank of a node is its position in a sorted list of the nodes.... 0 votes 0 votes Manas Mishra commented Nov 17, 2018 reply Follow Share 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 0 votes 0 votes Lakshman Bhaiya commented Nov 18, 2018 reply Follow Share @ Manas Mishra if I want to find the rank of $60?$ 0 votes 0 votes Manas Mishra commented Nov 18, 2018 reply Follow Share rank of 60 is 8 0 votes 0 votes Manas Mishra commented Nov 18, 2018 i edited by Manas Mishra Nov 18, 2018 reply Follow Share @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 votes 0 votes Somoshree Datta 5 commented Nov 18, 2018 reply Follow Share Manas Mishra rank of 60 should be 7 right? 0 votes 0 votes Manas Mishra commented Nov 18, 2018 reply Follow Share @somoshree no it will be 8 0 votes 0 votes Manas Mishra commented Nov 18, 2018 reply Follow Share @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 votes 0 votes kumar.dilip commented Nov 18, 2018 reply Follow Share @Somoshree Datta 5 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 votes 0 votes Lakshman Bhaiya commented Nov 18, 2018 reply Follow Share Why we take indexing from $1$, why not from $0?$ 0 votes 0 votes kumar.dilip commented Nov 18, 2018 reply Follow Share we can start with 0. But for the Rank of any node then we have to add one. 0 votes 0 votes Manas Mishra commented Nov 18, 2018 reply Follow Share @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 votes 0 votes Manas Mishra commented Nov 18, 2018 reply Follow Share @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 0 votes 0 votes Lakshman Bhaiya commented Nov 18, 2018 reply Follow Share In right skewed tree rank is $0?$ 0 votes 0 votes kumar.dilip commented Nov 18, 2018 reply Follow Share 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 0 votes 0 votes Manas Mishra commented Nov 18, 2018 reply Follow Share @lakshman in right skewed tree rank of root is zero if u use 0 based rank 0 votes 0 votes Please log in or register to add a comment.