The Gateway to Computer Science Excellence
0 votes
79 views

Consider the following

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

in DS by Veteran (55k points) | 79 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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
195,853 comments
102,227 users