# 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);
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:
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);
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: 