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

Malay Gain
Last Updated: May 13, 2022

Introduction

A node a is an ancestor of another node 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.

 

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

  1. What is the ancestor of a node?
    In a tree, node a is an ancestor of another node 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 is a descendant of a node 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 CodeStudio 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 CodeStudio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

 

Happy learning!

 

Was this article helpful ?
0 upvotes