Count Total No. of Ancestors in a Binary Search Tree

In a binary search tree, an ancestor of a node is any node on the path from the root to that node. Specifically, a node A is an ancestor of a node B if A is on the path from the root to B and A is higher than B in the tree (i.e., A is closer to the root). In other words, any node that is a parent, grandparent, great-grandparent, etc., of a node B in the tree is considered an ancestor of B.

The concept of ancestors is important in binary search trees because it is often useful to traverse the tree from the root to a particular node while keeping track of the ancestors along the way. This can be useful, for example, in algorithms that involve searching for a node, inserting a new node, or deleting a node from the tree.

Implementation

// Writing a C++ program to find out the above approach for the following
#include <bits/stdc++.h>
using namespace std;


// Writing a function to add an edge between the nodes u and v 
void add_edge(vector<int> adj[],
			int u, int v)
{
	adj[u].push_back(v);
	adj[v].push_back(u);
}


// Creating a function that will perform the DFS traversal for the following code and store the parent of each of the nodes. 
void dfs(vector<int>& parent,
		vector<int> adj[],
		int u,
		int par = -1)
{
	// we have to store the parent node
	parent[u] = par;


	// now, we will have to commute to the child node
	for (auto child : adj[u]) {


		// We have to recursively admit a function for the DFS traversal of the child node 
		if (child != par)
			dfs(parent, adj, child, u);
	}
}
// Creating a function that will count the total number of ancestors that has a smaller value than the current node
void countSmallerAncestors(
	vector<int> adj[], int n)
{
	// We have to store the parent of each node present 
	vector<int> parent(int(1e5), 0);


	// Now, we will perform the DFS traversal for each node.
	dfs(parent, adj, 1);


	// we have to traverse all the nodes present
	for (int i = 1; i <= n; i++) {


		int node = i;


		// Now, we have to store the total number of ancestors in the smaller node 
		int cnt = 0;


		// Loop until parent[node] != -1
		while (parent[node] != -1) {


// In case the condition of the program is satisfiable, and we have to increment the comment by 1. 
			if (parent[node] < i)
				cnt += 1;


			node = parent[node];
		}


		// Now, we have to print the result for the node that is present 
		cout << cnt << " ";
	}
}


// Writing the main code for the program above
int main()
{
	int N = 6;
	vector<int> adj[int(1e5)];


	// Tree Formation
	add_edge(adj, 1, 5);
	add_edge(adj, 1, 4);
	add_edge(adj, 4, 6);
	add_edge(adj, 5, 3);
	add_edge(adj, 5, 2);


	countSmallerAncestors(adj, N);


	return 0;
}

Output:

Example 2)

// Writing a Java program to find out the above approach for the following
import java.io.*;
import java.util.*;


class TPT{
// Writing a function to add an edge between the nodes u and v 
static void add_edge(ArrayList<ArrayList<Integer>> adj,
					int u, int v)
{
	adj.get(u).add(v);
	adj.get(v).add(u);
}
// Creating a function that will perform the DFS traversal for the following code and store the parent of each of the nodes. 
static void dfs(ArrayList<Integer> parent,
				ArrayList<ArrayList<Integer>> adj,
				int u, int par)
{
	// we have to store the parent node
	parent.set(u,par);


	// now, we will have to commute to the child node	
	for(int child : adj.get(u))
	{
// We have to recursively admit a function for the DFS traversal of the child node 
		if (child != par)
			dfs(parent, adj, child, u);
	}
}
// Creating a function that will count the total number of ancestors that has a smaller value than the current node
static void countSmallerAncestors(
	ArrayList<ArrayList<Integer>> adj, int n)
{
	// We have to store the parent of each node present 
	ArrayList<Integer> parent = new ArrayList<Integer>();
	for(int i = 0; i < (int)(1e5); i++)
	{
		parent.add(0);
	}


	// Now, we will perform the DFS traversal for each node.
	dfs(parent, adj, 1, -1);


	for(int i = 1; i <= n; i++)
	{
		int node = i;


	// Now, we have to store the total number of ancestors in the smaller node
		int cnt = 0;


		// Loop until parent[node] != -1
		while (parent.get(node) != -1)
		{
	// In case the condition of the program is satisfiable, and we have to increment the comment by 1. 
			if (parent.get(node) < i)
				cnt += 1;


			node = parent.get(node);
		}
		// Now we have to print the result for the node that is present 
		System.out.print(cnt + " ");
	}
}


// Writing the main code for the program above
public static void main (String[] args)
{
	int N = 6;
	ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	for(int i = 0; i < (int)(1e5); i++)
	{
		adj.add(new ArrayList<Integer>());
	}


	// Tree Formation
	add_edge(adj, 1, 5);
	add_edge(adj, 1, 4);
	add_edge(adj, 4, 6);
	add_edge(adj, 5, 3);
	add_edge(adj, 5, 2);


	countSmallerAncestors(adj, N);
}
}

Output:

Example 3)

// Writing a Python program to find out the above approach for the following
// Writing a function to add an edge between the nodes u and v 
def add_edge(u, v):
	
	global adj
	adj[u].append(v)
	adj[v].append(u)


// Creating a function that will perform the DFS traversal for the following code and store the parent of each of the nodes. 
def dfs(u, par = -1):
	
	global adj, parent
	// we have to store the parent node
	parent[u] = par


	// now, we will have to commute to the child node
	for child in adj[u]:
// We have to recursively admit a function for the DFS traversal of the child node 
		if (child != par):
			dfs(child, u)
// Creating a function that will count the total number of ancestors that has a smaller value than the current node
def countSmallerAncestors(n):
	global parent, adj
	// We have to store the parent of each node present 
	// Now, we will perform the DFS traversal for each node.
	dfs(1)
	// Now, we have to store the total number of ancestors in the smaller node
	for i in range(1, n + 1):
		node = i
// In case the condition of the program is satisfiable, and we have to increment the comment by 1. 
		cnt = 0


		# Loop until parent[node] != -1
		while (parent[node] != -1):
		// Now, we have to print the result for the node that is present 
			if (parent[node] < i):
				cnt += 1


			node = parent[node]


	// Now we have to print the result for the node that is present 
		print(cnt, end = " ")


// Writing the main code for the program above	
if __name__ == '__main__':
	
	N = 6
	adj = [[] for i in range(10**5)]
	parent = [0] * (10**5)


	# Tree Formation
	add_edge(1, 5)
	add_edge(1, 4)
	add_edge(4, 6)
	add_edge(5, 3)
	add_edge(5, 2)


	countSmallerAncestors(N)

Output:

Example 4)

// Writing a C# program to find out the above approach for the following
using System;
using System.Collections.Generic;
class TPT {
	// Writing a function to add an edge between the nodes u and v 
	static void add_edge(List<List<int>> adj, int u, int v)
	{
		adj[u].Add(v);
		adj[v].Add(u);
	}
// Creating a function that will perform the DFS traversal for the following code and store the parent of each of the nodes. 
	static void dfs(List<int> parent,
			List<List<int>> adj,
			int u,
			int par = -1)
	{
	// we have to store the parent node
		parent[u] = par;
	// now, we will have to commute to the child node
		foreach(int child in adj[u]) {
// We have to recursively admit a function for the DFS traversal of the child node 
			if (child != par)
				dfs(parent, adj, child, u);
		}
	}
// Creating a function that will count the total number of ancestors that has a smaller value than the current node
	static void countSmallerAncestors(
		List<List<int>> adj, int n)
	{
	// We have to store the parent of each node present 
		List<int> parent = new List<int>();
		for(int i = 0; i < (int)(1e5); i++)
		{
			parent.Add(0);
		}
	
	// Now, we will perform the DFS traversal for each node.
		dfs(parent, adj, 1);
	// Now we have to store the total number of ancestors in the smaller node
		for (int i = 1; i <= n; i++) {
	
			int node = i;
	
			// Store the number of ancestors
			// smaller than node
			int cnt = 0;
	
			// Loop until parent[node] != -1
			while (parent[node] != -1) {
// In case the condition of the program is satisfiable, and we have to increment the comment by 1. 
				if (parent[node] < i)
					cnt += 1;
	
				node = parent[node];
			}
		// Now we have to print the result for the node that is present 
			Console.Write(cnt + " ");
		}
	}


static void Main() {
	int N = 6;
	List<List<int>> adj = new List<List<int>>();
	for(int i = 0; i < (int)(1e5); i++)
	{
		adj.Add(new List<int>());
	}


	// Tree Formation
	add_edge(adj, 1, 5);
	add_edge(adj, 1, 4);
	add_edge(adj, 4, 6);
	add_edge(adj, 5, 3);
	add_edge(adj, 5, 2);


	countSmallerAncestors(adj, N);
}
}

Output:

Example 5)

<script>
// Writing a Javascript program to find out the above approach for the following
// Writing a function to add an edge between the nodes u and v 
function add_edge(adj, u, v)
{
	adj[u].push(v);
	adj[v].push(u);
}
// Creating a function that will perform the DFS traversal for the following code and store the parent of each of the nodes. 
function dfs(parent, adj, u, par = -1)
{
	// we have to store the parent node
	parent[u] = par;


	// now, we will have to commute to the child node
	adj[u].forEach(child => {		
	// We have to recursively admit a function for the DFS traversal of the child node 
		if (child != par)
			dfs(parent, adj, child, u);
	});
}
// Creating a function that will count the total number of ancestors that has a smaller value than the current node
function countSmallerAncestors(adj, n)
{
	// We have to store the parent of each node present 
	var parent = Array(100000).fill(0);


	// Now, we will perform the DFS traversal for each node.
	dfs(parent, adj, 1);


	// Now we have to store the total number of ancestors in the smaller node
	for (var i = 1; i <= n; i++) {


		var node = i;


// In case the condition of the program is satisfiable, and we have to increment the comment by 1. 
		var cnt = 0;


		// Loop until parent[node] != -1
		while (parent[node] != -1) {


// Now we have to print the result for the node that is present 
			if (parent[node] < i)
				cnt += 1;


			node = parent[node];
		}


		// Print the required result
		// for the current node
		document.write( cnt + " ");
	}
}


// Writing the main code for the program above
var N = 6;
var adj = Array.from(Array(100000), ()=>Array());


// Tree Formation
add_edge(adj, 1, 5);
add_edge(adj, 1, 4);
add_edge(adj, 4, 6);
add_edge(adj, 5, 3);
add_edge(adj, 5, 2);
countSmallerAncestors(adj, N);




</script>

Output: