Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

# Longest Consecutive Sequence In A Binary Tree

Moderate
0/80
Average time to solve is 15m
Contributed by
5 upvotes
Asked in companies

## Problem statement

Given a binary tree, return the length of the longest path which has consecutive integers in increasing order from root to leaves. A path is defined as a sequence of nodes which share an edge between them.

For example:

The path shown in red is the longest increasing consecutive Path in the tree. We can see that it has 4 nodes (4,5,6,7) which are consecutive integers. Hence the answer for this tree will be 4.

Note that there is another consecutive sequence of length 3 i.e. 1->2->3 in the left subtree of the root node, but it is not the longest consecutive path.

Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 100
1 <= N <= 3000

Where ‘N’ is the number of nodes in the given binary tree.

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````2
6 4 7 -1 -1 -1 8 9  -1 -1 -1
1 2 3 4 5 6 7 - 1 -1 -1 -1 -1 -1 -1 -1
``````
##### Sample Output 1 :
``````4
2
``````
##### Explanation Of Sample Input 1 :
``````Test Case 1:
The tree is:
``````

``````We can clearly see that the longest path has the length 4 (6->7->8->9) hence we return 4.

Test Case 2:
The Tree is:
``````

``````We can see that the longest consecutive sequence, in this case, has length 2 i.e 1->2.
Therefore we return 2
``````
##### Sample Input 2 :
`````` 2
1 2 9 3 4 5 6 4 -1 -1 -1 -1 -1 -1 -1 -1 -1
10 11 -1 12 -1 13 -1 16 -1 17 -1 38 -1 14 -1 -1 -1
``````
##### Sample Output 2 :
``````4
7
``````
Console