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

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

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

{
// 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
}
}
}``````

## Code

``````// C++ implementation of above approach

#include<bits/stdc++.h>
using namespace std;

int max_diff=INT_MIN;

{
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();

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

{
// 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
}
}
}

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

int root;
for(int i=0;i<n;i++)
{
if(p[i]==-1)
{
root=i+1;
continue;
}
else
{
}

}

//for assigning ancestor numbers to each node

vector<int> ancestor(n+1,0);

//dfs for finding the max difference on

vector<int> visited(n+1,0);

for(int i=1;i<=n;i++)
{
}

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!

Live masterclass