Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
4.
Code
5.
Complexity analysis
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Malay Gain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

 

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

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

 

Previous article
Find the Roots of a Tree that gives Minimum Height
Next article
Tarjan’s Algorithm to find Strongly Connected Components
Live masterclass