Logo
×

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:

Finding Rank in a Binary Search Tree

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:

Finding Rank in a Binary Search Tree

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:

Finding Rank in a Binary Search Tree

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:

Finding Rank in a Binary Search Tree

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:

Finding Rank in a Binary Search Tree

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:

Finding Rank in a Binary Search Tree

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:

Finding Rank in a Binary Search Tree

Related Topics

FLEX (Fast Lexical Analyzer Generator)

FLEX stands for Fast Lexical Analyzer Generator. Around 1987, Vern Paxson created Flex in C with a great deal of input and inspiration from Van Jacobson. Van Jacobson's approach is...

3 minutes read.

Boruvkas algorithm

This algorithm is used for finding minimum spanning tree from a weighted graph. Like prim’s and kruskal’s algorithm it is also a greedy algorithm. Note:What is the minimum spanning tree?We know...

4 minutes read.

Given a Binary Tree Check the Zig-Zag Traversal

Implementation // The C++ implementation of the zig-zag traversal method in the O(n) time.  #include <iostream> #include <stack> using namespace std; // creating a binary tree node. struct __nod { int record; struct __nod *Lft, *Rt; }; // creating a...

4 minutes read.

Data structure: Infix to Prefix Conversion

Infix to Prefix Conversion In present time, we use the infix expression in our daily life but the computers are not able to understand this format because they need to keep...

4 minutes read.

Tree terminology in Data structures

Data structures The storage used to organize and store data is known as a data structure, and it is a method where data can be arranged on a computer to be...

6 minutes read.

Linear vs Circular Queue: Data Structure

Difference Between Linear and Circular Queue What is Linear Queue? A linear queue is linear data structure which works on first in first out principle. We can say a linear queue is...

3 minutes read.

Binary Search

Binary Search: When there is a large data structure, the linear search takes a lot of time to search the element. The binary search was developed to overcome the lack...

7 minutes read.

Cocktail Sort

C Program executes cocktail sort. Combo sort is a somewhat straightforward arranging calculation initially planned by Wlodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered by Stephen Lacey and Richard Box...

5 minutes read.

Find all possible words from board

We have been given a dictionary of words and a board of characters from which we can form strings. Now, we have to check if the string is present in...

5 minutes read.

Optimal binary search tree using dynamic programming

Implementation // We are creating a presentation where we will present a recursive method of the optimal binary search tree problem.  #include <bits/stdc++.h> using namespace std; //creating a utility function that will help us...

9 minutes read.

Remove duplicates from an unsorted Linked List

Remove duplicates from an unsorted Linked List This article will explain how we can remove duplicates from unsorted linked lists. Here we have given an unsorted singly linked list and will...

3 minutes read.

Given a Generate all Structurally Unique Binary Search Trees

Implementation // Creating a C++ program that will help us build all the binary search trees for the keys from 1 to n.  #include <bits/stdc++.h> using namespace std; // creating a structure that will...

8 minutes read.

Semi-Structured data

In this article, we will discuss the semi-structured data. Data can be defined as the distinct piece of information that is gathered and translated for some purpose. It can be...

5 minutes read.

CSS Text-indent

Text-indent The Text-indent property of CSS is used to set any first line’s indentation inside a text’s block. It describes the horizontal space amount that puts establish before the text line. It...

3 minutes read.

Sum of Nodes in a Binary Tree

In this article, we will see the sample problems that will help us understand the concept and summation of all the nodes in the binary tree. Implementation /* creating a program that...

4 minutes read.

Hashing and its Applications

Hashing Hashing refers to transforming plain text data in such a way that even if it is leaked for some reason, no one would be able to make sense of it....

6 minutes read.

Union and Intersection of two Linked Lists

Union and Intersection of two Linked Lists This article explains how we can do the union and intersection of two linked lists. In this problem, we have given two linked lists...

3 minutes read.

What is the difference between DFS and BFS?

What is BFS? BFS is generally known as the low level traversal. As we already know that it stands for breadth first search and is mainly used in the queue data...

4 minutes read.

What is a Height-Balanced Tree in Data Structure

A height-balanced tree is a type of binary tree. If the absolute difference between the heights of the left and right subtree is less than or equal to 1, then...

6 minutes read.

Linear Queue Data Structure in C

Data Structure There are many ways to store data in programming, that Queue has features that make it all the more special. We all know that data structure is a way...

9 minutes read.