search
Log In
0 votes
157 views

Consider the following

What is the rank(index) of the node $50?$

in DS 157 views
0
Is it 6?
0
how can you explain, I never heard about the rank of the index?
0

I found it here pls check  & varify.

0
thanks
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
answer is $6$
0
Rank of a node is its position in a sorted list of the nodes....
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
0

Manas Mishra

if I want to find the rank of $60?$

0
rank of 60 is 8
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

Manas Mishra rank of 60 should be 7 right?

0
@somoshree no it will be 8
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

@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
Why we take indexing from $1$, why not from $0?$
0
we can start with 0. But for the Rank of any node then we have to add one.
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
0
In right skewed tree rank is $0?$
0
@lakshman

in right skewed tree rank of root is zero if u use 0 based rank

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
72 views
what will be differnece if we use c)option and d) option explain ??
asked Jan 13, 2017 in DS focus _GATE 72 views
0 votes
0 answers
2
99 views asked Dec 6, 2016 in DS Vishal Goyal 99 views
0 votes
0 answers
3
498 views
I am sitting at home and preparing.Started in month of September.I have been taken test series of X popular institute.I have answered 2 part subject tests of toc and scored around 41% in the first one and 30% in the second test.Please help me to improve my condition ... year.Scored 20 in last years Gate with no preparation at all.I am general.Please suggest me strategy to get the best from here.
asked Oct 16, 2018 in GATE sripo 498 views
1 vote
0 answers
4
148 views
Which of the following statements are correct? S1: Binary search on array take less time than binary search on linked list. S2: Merge sort on array has more space complexity than merge sort on linked list. Only S1 Only S2 Both S1 and S2 Neither S1 nor S2 ** Here my doubt is, In S1 should i assume here that array is sorted. Answer given as Both S1 and S2.
asked Dec 27, 2015 in DS Sandeep Singh 148 views
...