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

Difference Between Linear and Non Linear Data Structures

Data Structure A data structure is a data object together with the relationships between the instances and the individual elements that compose an instance. These relationships are defined by the operations...

5 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.

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.

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.

Trim a binary search tree

Implementation //writing a C++ program will help us eliminate the keys that are out of the league.  #include<bits/stdc++.h> using namespace std; //we are now creating a binary search tree node consisting of key left...

8 minutes read.

Given a Binary Tree Swap Nodes at K Height

Implementation // Writing a C++ program that will help us exchange the nodes.  #include<bits/stdc++.h> using namespace std; // Creating a binary tree node. struct __nod { int record; struct __nod *Lft, *Rt; }; // creating a function that will help...

8 minutes read.

Convert Binary Tree into a Threaded Binary Tree

Implementation /*Writing a C++ program that will help us change the binary tree into a threaded binary tree and help us transform. */ #include <bits/stdc++.h> using namespace std; /*Creating the structure of a node...

11 minutes read.

Write Main Difference Between Tree and Graph in Data Structures

Graph: The graph has two sets, which are considered V and E. These vertices are also called nodes, and edges are referred to as arcs connecting any two nodes in a...

4 minutes read.

Merge Sort

Merge Sort is one of the most widely used sorting algorithms, and it is based on the Divide and Conquer principle. A problem is subdivided into multiple sub-problems in this method....

8 minutes read.

DFS (Depth-first search) Algorithm: Data Structure

What is DFS (Depth-first search)? The depth first search is a graph traversal algorithm. The idea behind this algorithm is backtracking and it is a kind of recursive algorithm. In the...

3 minutes read.

Asynchronous advantage actor-critic (A3C) Algorithm

The Asynchronous advantage actor-critic (A3C) Algorithm is one of the latest algorithms developed by the Artificial Intelligence division, Deep Mind at Google. It is used for the Deep Reinforcement Learning...

3 minutes read.

Collision Resolution Techniques

Collision Resolution Techniques Collision in hashing In this, the hash function is used to compute the index of the array.The hash value is used to store the key in the hash table,...

2 minutes read.

Bubble Sort vs Selection Sort

In this article, we will discuss the basic differences between these two sorting algorithms. Let us have a quick overview of what these sorting algorithms are? And what are the...

6 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.

Bubble Sort vs Quick Sort

In this article, we are going to compare two sorting techniques, Bubble sort and Quick Sort. In starting, we will first discuss the idea of sorting an array using bubble...

7 minutes read.

Inorder Successor in Binary Trees

The next node in the Inorder traversal of a binary tree is known as Inorder successor of that particular node. In a Binary Search Tree, the definition of Inorder successor can...

9 minutes read.

Properties of Binary Tree

Trees are maybe of the most significant datum structures. They are used to store and figure out data. A binarytree is a tree data structure made from nodes, all of which has...

3 minutes read.

Recursion in Fibonacci

Fibonacci heap is considered to be a particular execution of the heap data structure that ultimately helps in making use of not just any number but the Fibonacci numbers. It...

3 minutes read.

Trie data structure

Trie data structure The term “trie” comes from the word “retrieval” which means getting information. The trie data structure is a sorted extension of tree-based data structure. The trie data structure...

5 minutes read.

Doubly Linked List

Doubly Linked List Doubly linked list is another kind of Linked list. Doubly linked list contains two pointers for navigation. In this, we can traverse the list in both directions, either...

4 minutes read.