# Finding Rank in a Binary Search Tree

### Implementation

```
// writing a C++ program to find out the rank and element in the program.
#include <bits/stdc++.h>
using namespace std;
struct __nod {
int record;
__nod *Lft, *Rt;
int LftSize;
};
__nod* new__nod(int record)
{
__nod *temp = new __nod;
temp->record = record;
temp->Lft = temp->Rt = NILL;
temp->LftSize = 0;
return temp;
}
// we are now inserting a new node in the list.
__nod* insert(__nod*& root, int record)
{
if (!root)
return new__nod(record);
// we have to update the size of the left subtree.
if (record <= root->record) {
root->Lft = insert(root->Lft, record);
root->LftSize++;
}
else
root->Rt = insert(root->Rt, record);
return root;
}
// we are creating a fully new function that will help us get the rank of a node named x.
int getRank(__nod* root, int x)
{
// point 1.
if (root->record == x)
return root->LftSize;
// Point 2.
if (x < root->record) {
if (!root->Lft)
return -1;
else
return getRank(root->Lft, x);
}
// Point 3.
else {
if (!root->Rt)
return -1;
else {
int RtSiz = getRank(root->Rt, x);
if(RtSiz == -1 ) return -1;
return root->LftSize + 1 + RtSiz;
}
}
}
// writing the main code to test the above functions.
int main()
{
int arry[] = { 5, 1, 4, 4, 5, 9, 7, 13, 3 };
int n = sizeof(arry) / sizeof(arry[0]);
int x = 4;
__nod* root = NILL;
for (int i = 0; i < n; i++)
root = insert(root, arry[i]);
cout << "Rank of " << x << " in stream is: "
<< getRank(root, x) << endl;
x = 13;
cout << "Rank of " << x << " in stream is: "
<< getRank(root, x) << endl;
x = 8;
cout << "Rank of " << x << " in stream is: "
<< getRank(root, x) << endl;
return 0;
}
```

**Output:**

**Example 2**

```
// writing a C# program to find out the rank and element in the program.
using System;
class TFT
{
public class __nod
{
public int record;
public __nod Lft, Rt;
public int LftSize;
}
static __nod new__nod(int record)
{
__nod temp = new __nod();
temp.record = record;
temp.Lft = NILL;
temp.Rt = NILL;
temp.LftSize = 0;
return temp;
}
// we are now inserting a new node in the list.
static __nod insert(__nod root, int record)
{
if (root == NILL)
return new__nod(record);
// we have to update the size of the left subtree.
if (record <= root.record)
{
root.Lft = insert(root.Lft, record);
root.LftSize++;
}
else
root.Rt = insert(root.Rt, record);
return root;
}
// we are creating a fully new function that will help us get the rank of a node named x.
static int getRank(__nod root, int x)
{
// Point 1.
if (root.record == x)
return root.LftSize;
// Point 2.
if (x < root.record)
{
if (root.Lft == NILL)
return -1;
else
return getRank(root.Lft, x);
}
// Point 3.
else
{
if (root.Rt == NILL)
return -1;
else
{
int RtSiz = getRank(root.Rt, x);
if(RtSiz == -1) return -1;
return root.LftSize + 1 + RtSiz;
}
}
}
// writing the main code to test the above functions.
public static void Main(String[] args)
{
int []arry = { 5, 1, 4, 4, 5, 9, 7, 13, 3 };
int n = arry.Length;
int x = 4;
__nod root = NILL;
for (int i = 0; i < n; i++)
root = insert(root, arry[i]);
Console.WriteLine("Rank of " + x +
" in stream is : " +
getRank(root, x));
x = 13;
Console.WriteLine("Rank of " + x +
" in stream is: " +
getRank(root, x));
}
}
```

**Output:**

**Example 3**

```
# Write a Python program to find out the rank and element in the program.
class new__nod:
def __init__(self, record):
self.record = record
self.Lft = self.Rt = None
self.LftSize = 0
# We are now inserting a new node in the list.
def insert(root, record):
if root is None:
return new__nod(record)
# We have to update the size of the left subtree.
if record <= root.record:
root.Lft = insert(root.Lft, record)
root.LftSize += 1
else:
root.Rt = insert(root.Rt, record)
return root
# We are creating a fully new function that will help us in getting the rank of a node named x.
def getRank(root, x):
# Point 1.
if root.record == x:
return root.LftSize
# Point 2.
if x < root.record:
if root.Lft is None:
return -1
else:
return getRank(root.Lft, x)
# Point 3.
else:
if root.Rt is None:
return -1
else:
RtSiz = getRank(root.Rt, x)
if RtSiz == -1:
# x not found in Rt sub tree, i.e. not found in stream
return -1
Else:
return root.LftSize + 1 + RtSiz
# Writing the main code to test the above functions.
if __name__ == '__main__':
arry = [5, 1, 4, 4, 5, 9, 7, 13, 3]
n = len(arry)
x = 4
root = None
for i in range(n):
root = insert(root, arry[i])
print("Rank of", x, "in stream is:",
getRank(root, x))
x = 13
print("Rank of", x, "in stream is:",
getRank(root, x))
x = 8
print("Rank of", x, "in stream is:",
getRank(root, x))
```

**Output:**

**Example 4**

```
// writing a Java program to find out the rank and element in the program.
class TFT {
static class __nod {
int record;
__nod Lft, Rt;
int LftSize;
}
static __nod new__nod(int record)
{
__nod temp = new __nod();
temp.record = record;
temp.Lft = NILL;
temp.Rt = NILL;
temp.LftSize = 0;
return temp;
}
// we are now inserting a new node in the list.
static __nod insert(__nod root, int record)
{
if (root == NILL)
return new__nod(record);
// we have to update the size of the left subtree.
if (record <= root.record) {
root.Lft = insert(root.Lft, record);
root.LftSize++;
}
else
root.Rt = insert(root.Rt, record);
return root;
}
// we are creating a fully new function that will help us get the rank of a node named x.
static int getRank(__nod root, int x)
{
// Point 1.
if (root.record == x)
return root.LftSize;
// Point 2.
if (x < root.record) {
if (root.Lft == NILL)
return -1;
else
return getRank(root.Lft, x);
}
// Point 3.
else {
if (root.Rt == NILL)
return -1;
else {
int RtSiz = getRank(root.Rt, x);
if(RtSiz == -1) return -1;
return root.LftSize + 1 + RtSiz;
}
}
}
// writing the main code to test the above functions.
public static void main(String[] args)
{
int arry[] = { 5, 1, 4, 4, 5, 9, 7, 13, 3 };
int n = arry.length;
int x = 4;
__nod root = NILL;
for (int i = 0; i < n; i++)
root = insert(root, arry[i]);
System.out.println("Rank of " + x + " in stream is : "+getRank(root, x));
x = 13;
System.out.println("Rank of " + x + " in stream is : "+getRank(root, x));
}
}
```

**Output:**

**Example 5**

```
<script>
// writing a Javascript program to find out the rank and element in the program.
class __nod
{
constructor()
{
this.record = 0;
this.Lft = NILL;
this.Rt = NILL;
this.LftSize = 0;
}
}
function new__nod(record)
{
var temp = new __nod();
temp.record = record;
temp.Lft = NILL;
temp.Rt = NILL;
temp.LftSize = 0;
return temp;
}
// we are now inserting a new node in the list.
function insert(root, record)
{
if (root == NILL)
return new__nod(record);
// we have to update the size of the left subtree.
if (record <= root.record)
{
root.Lft = insert(root.Lft, record);
root.LftSize++;
}
else
root.Rt = insert(root.Rt, record);
return root;
}
// we are creating a fully new function that will help us get the rank of a node named x.
function getRank(root, x)
{
// Point 1.
if (root.record == x)
return root.LftSize;
// Point 2.
if (x < root.record)
{
if (root.Lft == NILL)
return -1;
else
return getRank(root.Lft, x);
}
// Point 3.
else
{
if (root.Rt == NILL)
return -1;
else
{
var RtSiz = getRank(root.Rt, x);
if(RtSiz == -1) return -1;
return root.LftSize + 1 + RtSiz;
}
}
}
// writing the main code to test the above functions.
var arry = [5, 1, 4, 4, 5, 9, 7, 13, 3];
var n = arry.length;
var x = 4;
var root = NILL;
for (var i = 0; i < n; i++)
root = insert(root, arry[i]);
document.write("Rank of " + x +
" in stream is: " +
getRank(root, x) + "<br>");
x = 13;
document.write("Rank of " + x +
" in stream is: " +
getRank(root, x)+"<br>");
x = 8;
document.write("Rank of " + x +
" in stream is: " +
getRank(root, x));
</script>
```

**Output:**

**Example 6**

```
// writing a C++ program to find out the rank and element in the program.
#include <bits/stdc++.h>
using namespace std;
// writing the main code of the program to test the above functions.
int main()
{
int a[] = {5, 1, 14, 4, 15, 9, 7, 20, 11};
int key = 20;
int arryaySize = sizeof(a)/sizeof(a[0]);
int count = 0;
for(int i = 0; i < arryaySize; i++)
{
if(a[i] <= key)
{
count += 1;
}
}
cout << "Rank of " << key << " in stream is: "
<< count-1 << endl;
return 0;
}
```

**Output:**

**Example 7**

```
// writing a C# program to find out the rank and element in the program.
using System;
class TFT
{
// writing the main code to test the above functions.
public static void Main()
{
int []a = {5, 1, 14, 4, 15, 9, 7, 20, 11};
int key = 20;
int arryaySize = a.Length;
int count = 0;
for(int i = 0; i < arryaySize; i++)
{
if(a[i] <= key)
{
count += 1;
}
}
Console.WriteLine("Rank of " + key +
" in stream is: " +
(count - 1));
}
}
```

**Output:**