A node a is an ancestor of another node b if b is a child of node a or any child of node a is an ancestor of node b. In simple words, all the nodes present on the path from the root of the tree to node b are called ancestors of b. From the title of the article, it can be understood that we need to find the maximum difference between two nodes such that one is the ancestor of another.

Problem statement

Consider a generic tree with n nodes denoted by numbers from 1 to n. You are given an array p[ ] where ith element denotes the parent node of the ith node and another array w[ ] where the ith element is the weight of the ith node. In both cases, we have considered 1-base indexing the array. Find the maximum difference between weights of two nodes such that one is the ancestor of another.

Input

w[] = {5,10,6,12}
p[] = {2,-1,4,2}

Output

Max_diff = 6

Explanation

node 4 is an ancestor of node 3. So, max difference = 12 - 6 = 6

Note: Please try to solve the problem first and then see the below solution approach.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach

Before solving the problem, we need to represent the generic tree as adjacency list. We will use the p[ ] array to construct the adjacency list.

In the next step, we will mark each node with a number (ancestor number)to identify if a node is ancestor of another. Here we will use BFS approach to mark each node at a same level with the same number. Root will be marked as 0, nodes of next level will be marked as 1,then 2. This way ancestor number will be increasing with levels.

void bfs(int root,vector<int> adj[],vector<int> &ancestor)
{
int n=ancestor.size()-1;
//stroring if a node visited or not
vector<int> visited(n+1,0);
//queue for dfs
queue<int> q;
visited[root]=1;
q.push(root);
while(!q.empty())
{
int f=q.front();
q.pop();
for(auto neighbour:adj[f])
{
if(!visited[neighbour])
{
visited[neighbour]=1;
//storing ancestor number for the neighbours of source node f
ancestor[neighbour]=ancestor[f]+1;
q.push(neighbour);
}
}
}
}

Now if we apply DFS Algorithm from a source node, the nodes with greater ancestor number found are having source node as their ancestor.

This way we will apply DFS from each node, and will find the differences of weight between the source node and nodes whose ancestor is the source node. Thus maximum difference of weight between two nodes such that one is the ancestor of another will be found.

//dfs from node src
int max_diff=INT_MIN;
void dfs(int src,vector<int> adj[],int w[],vector<int> ancestor,vector<int> vis)
{
vis[src]=1;
for(auto n:adj[src])
{
// if current node not visited and src is an ancestor of the current node
if(!vis[n] && ancestor[n]>ancestor[src])
{
//storing max of previous max differnce
//and difference bwtween src node and current node
max_diff=max(max_diff,w[src-1]-w[n-1]);
//recursive dfs call from current node
dfs(n,adj,w,ancestor,vis);
}
}
}

Code

// C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
int max_diff=INT_MIN;
void bfs(int root,vector<int> adj[],vector<int> &ancestor)
{
int n=ancestor.size()-1;
//stroring if a node visited or not
vector<int> visited(n+1,0);
//queue for dfs
queue<int> q;
visited[root]=1;
q.push(root);
while(!q.empty())
{
int f=q.front();
q.pop();
for(auto neighbour:adj[f])
{
if(!visited[neighbour])
{
visited[neighbour]=1;
//storing ancestor number for the neighbours of source node f
ancestor[neighbour]=ancestor[f]+1;
q.push(neighbour);
}
}
}
}
//dfs from node src
void dfs(int src,vector<int> adj[],int w[],vector<int> ancestor,vector<int> vis)
{
vis[src]=1;
for(auto n:adj[src])
{
// if current node not visited and src is an ancestor of the current node
if(!vis[n] && ancestor[n]>ancestor[src])
{
//storing max of previous max differnce
//and difference bwtween src node and current node
max_diff=max(max_diff,w[src-1]-w[n-1]);
//recursive dfs call from current node
dfs(n,adj,w,ancestor,vis);
}
}
}
//driver code
int main()
{
int n=4;
int w[n]={5,10,6,12};
int p[n]={2,-1,4,2};// parent of ith node ; 1-indexed
//adjacency list of the tree
vector<int> adj[n+1];
int root;
for(int i=0;i<n;i++)
{
if(p[i]==-1)
{
root=i+1;
continue;
}
else
{
adj[i+1].push_back(p[i]);
adj[p[i]].push_back(i+1);
}
}
//for assigning ancestor numbers to each node
vector<int> ancestor(n+1,0);
bfs(root,adj,ancestor);
//dfs for finding the max difference on
vector<int> visited(n+1,0);
for(int i=1;i<=n;i++)
{
dfs(i,adj,w,ancestor,visited);
}
cout<<max_diff;
}

Output

maximum difference of wieght between two such nodes : 6

Complexity analysis

Time Complexity of the above approach is O(n2).

Space complexity is O(n).

FAQs

What is the ancestor of a node? In a tree, node a is an ancestor of another node b if b is a child of node a or any child of node a is an ancestor of node b.

What descendant of a node? A node p is a descendant of a node q if q is an ancestor of the node p.

Key Takeaways

This article covered how to maximize the difference between pair of nodes in a given rooted tree such that one node is the ancestor of another.

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.