Longest Path

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in company
Google inc

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
1 1 1 2 2
1 2 3 4 5 -1 -1 -1 -1 -1 -1
3
1 1 1
2 3 1 -1 -1 -1 -1
Sample Output 1 :
2
2
Explanation For Sample Input 1 :
For first test case the tree will be :


The longest path with nodes having the same weight is : (2 1 3).
Length of longest path is  : 2.

For second test case tree will be :


The longest path with nodes having the same weight is : (3  2 1).
Length of longest path is : 2.
Sample Input 2 :
1
3
1 2 3
2 3 1 -1 -1 -1 -1
Sample Output 2 :
0
Hint

Think of traversing each node

Approaches (2)
Depth - First Search

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 :

 

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

HELPER(‘ROOT’, ‘RES’):
 

  1. If ‘ROOT’ is equal to ‘NULL’.
    1. Return 0.
  2. 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’)
  3. Update ‘RES’ by the maximum of ‘RES’ and ‘TEMP’.
  4. Call the left and right subtrees recursively to traverse other nodes.

 

DFS(‘ROOT’, ‘WT’):
 

  1. If ‘ROOT’ is equal to ‘NULL’.
    • Return 0.
  2. 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.
  3. Else, return 0.
Time Complexity

O(N^2), where ‘N’ is the number of nodes in the tree.

 

We traverse each node of the binary tree, and for each node, we traverse at max all the nodes of the binary tree to find the longest path. Therefore, the overall time complexity will be O(N^2).

Space Complexity

O(N), where ‘N’ is the number of nodes in the tree.

 

Recursive stack can contain at most ‘N’ nodes of the binary tree .Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Longest Path
Full screen
Console