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