Last Updated: 3 Sep, 2021

Longest Path

Moderate

Asked in company

Solve now

Problem statement

You have been practicing on the topic binary tree for a few days. Your friend challenges you by giving you a binary tree with ‘N’ nodes in which each node has a weight associated with it and asks you to find the largest number of edges such that the nodes connecting those edges have the same weight.

Note :

1. Two nodes may have the same value associated with it.
2. The root node will be fixed and will be provided in the function.

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer 'N', representing the number of nodes in the tree.

The second line of each test contains the ‘N’ single space-separated integers representing weight of each node in level order form.

The third line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for 'NULL' node) Refer to the example for further clarification.

Example :

Consider the binary tree

The input of the tree depicted in the image above will be like : 
1 2 2 3 4 5 3
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1
The weight of the root node is 1.

Level 2 :
Left child of 1 = 2
Weight of left child of 1 = 2
Right child of 1 = 3
Weight of right child of 1 = 2

Level 3 :
Left child of 2 = 4
Weight of left child of 2 = 3
Right child of 2 = null (-1)
Left child of 3 = 5
Weight of left child of 3 = 4
Right child of 3 = 6
Weight of right child of 3 = 5

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Weight of right child of 4 = 3
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Output Format :

For each test case, print a single integer representing the number of edges in the longest path.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^3
1 <= NODE[i] <= 10^4
1 <= WEIGHT[i] <= N

Where NODE[i] is the data of ‘ith’ node and WEIGHT[i] is weight of ‘ith’ node. 

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The basic idea is to traverse each node of the tree and perform a depth-first search on that node to find the number of edges that have the same weight.

Here is the algorithm :

Create a variable (say, ‘RES’) that will store the length of the longest path and initialize it with 0.
Call the HELPER function to find the longest length.
Finally, return ‘RES’.

HELPER(‘ROOT’, ‘RES’):

If ‘ROOT’ is equal to ‘NULL’.
1. Return 0.
Call DFS function on left and right subtree by passing the weight of the current node and store the sum of their result in a variable (say, ‘TEMP’)
Update ‘RES’ by the maximum of ‘RES’ and ‘TEMP’.
Call the left and right subtrees recursively to traverse other nodes.

DFS(‘ROOT’, ‘WT’):

If ‘ROOT’ is equal to ‘NULL’.
- Return 0.
Check if weight of ‘ROOT’ is equal to ‘WT’
- Return 1 + maximum of ‘DFS(ROOT -> LEFT, WT)’ and ‘DFS(ROOT -> RIGHT, WT)’ to find the maximum nodes with same weight in left and right subtrees.
Else, return 0.

Solve now

02 Approach

The optimization is to traverse the tree while checking the weight of the nodes. For each node, the length of the longest path, including the node itself, will be 1 + longest length in the left subtree and the right subtree condition being the weights of the nodes are equal.

Here is the algorithm :

Create a variable (say, ‘RES’) that will store the length of the longest path and initialize it with 0.
Call the HELPER function to find the longest length.
Finally, return ‘RES’.

HELPER(‘ROOT’, ‘RES’):

If ‘ROOT’ is equal to ‘NULL’.
- Return 0.
Call the left subtree recursively and store the longest path of the left subtree in a variable (say, ‘lMax’).
Similarly, call the right subtree recursively and store the longest path of the right subtree in a variable (say, ‘rMAX’).
Create two variables (say, ‘lTemp’ and ‘rTemp’) to store the left and right subtrees answers.
Check if the ‘LEFT’ of ‘ROOT’ exists and the weight of the ‘LEFT’ node is equal to the weight of the ‘ROOT’ node.
- Update ‘lTemp’ by 1 + ‘lMax’.
Check if the ‘RIGHT’ of ‘ROOT’ exists and the weight of the ‘RIGHT’ node is equal to the weight of the ‘ROOT’ node.
- Update ‘rTemp’ by 1 + ‘rMax’.
Update ‘RES’ by the maximum of ‘RES’ and ‘lTemp’ + ‘rTemp’.
Finally, return the maximum of ‘lTemp’ and ‘rTemp’.

Solve now