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: