Maximize Difference between pair of Nodes in a given rooted Tree such that one Node is Ancestor of another

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);
			}
	    }
	}
}

You can also try this code with Online C Compiler

Run Code

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);
		}
	}
}

You can also try this code with Online C Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

maximum difference of wieght between two such nodes : 6

You can also try this code with Online C++ Compiler

Run Code

Complexity analysis

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

Space complexity is O(n).

FAQs

1. 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.
    
2. 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.

Check out this problem - Pair Sum In Array.

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. 

Happy learning!