Longest Consequence

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote
Asked in companies
BytedanceGoogle inc

Problem statement

You are given a binary tree consisting of ‘N’ nodes. Each node has an integer value assigned to it. Ninja recently learned about tree algorithms and the teacher gave him an assignment on it.

You need to find the length of the longest path in this tree which comprises nodes with consecutive values in increasing order. Every node is considered a path of length 1.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse).

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 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 -1 4 5
-1 3 -1 -1 -1 -1
-1 -1

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

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

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

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Value 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, output an integer denoting the length of the longest path in the tree which comprises nodes with consecutive values in increasing order

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= Node[i] <= 10^5
Sum of N over all Test cases <= 10^5

Time Limit : 1 sec
Sample Input 1 :
2
4
2 -1 3 2 -1 1 -1 -1 -1
5
1 -1 3 2 4 -1 -1 -1 5 -1 -1
Sample Output 1 :
2
3
Explanation Of Sample Input 1 :
For test case 1 we have, 

The input tree looks like : 


The longest path is 2 - 3 consisting of vertices 1 and 2.    

Note that the path 3 - 2 - 1 is not valid.

So, we output 2.

For test case 2 we have,

The input tree looks like : 


The longest path is 3 - 4 - 5.

So, we output 3.
Sample Input 2 :
2
5
2 2 -1 3 1 -1 4 -1 -1 -1 -1 
4
4 1 -1 1 1 -1 -1 -1 -1
Sample Output 2 :
3
1
Hint

 Think about implementing DFS to solve the problem.

 

Approaches (1)
Optimal Approach

 

Approach : 
 

  • Notice the fact that if we know the path of the longest sequence then it is unnecessary to check if each of the vertices can be the starting point of the path as it is best to start the path from the smallest value point.
  • So, we pass the root to the DFS function and for each vertex check if its value is 1 greater than its parent value.
  • If yes, we continue the path from the parent vertex.
  • Else, this is the new path of length 1.
  • We recursively call the children of the current vertex and check.
  • We return the maximum path length we obtain.


 

Algorithm : 

 

  • Initialise a global variable ‘ans’ = 0.
  • Pass the root node and a variable ‘len=0’ to function ‘dfs’.
    • Check if the value of the root node is 1 greater than the parent node.
    • If yes, increment ‘len’.
    • Else, update ‘len’ = 1.
    • Update ‘ans’ as the maximum of ‘ans’ and ‘len’.
  • Return ‘ans’ as the final result.

 

Time Complexity

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

We are traversing each vertex only once, so the overall time complexity is O(N).

 

Space Complexity

O(1)
 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

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