Given a Binary Tree find the length of the longest path which comprises of connected nodes with consecutive values in increasing order. 
 
Example 1:
Input :      
           1                               
         /   \                          
        2     3                      
Output: 2
Explanation : Longest sequence is 1, 2.
 
Example 2:
Input :    
            10                               
         /     \                          
       20       30                      
      /  \      /
     40      60   90    
Output :  -1
Explanation: For the above test case no 
sequence is possible. So output is -1.
 
Your Task:  
You dont need to read input or print anything. Complete the function longestConsecutive() which takes root node as input parameter and returns the length of the longest consecutive increasing sequence (of at least length 2) in the given Binary Tree. If such a sequence does not exist, return -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of Tree)
Constraints:
1 ≤ N ≤ 10^3

Source: geeksforgeeks | Difficulty: EASY

Starter code: '''
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
'''
class Solution:
    # your task is to complete this function
    # function should print the top view of the binary tree
    # Note: You aren't required to print a new line after every test case
    def longestConsecutive(self, root):
        # Code here


Solutions:
res = 0

class Solution:

	def longConsUtil(self, root, curlength, expected):
		if root is None:
			return
		if root.data == expected:
			curlength += 1
		else:
			curlength = 1
		global res
		res = max(res, curlength)
		self.longConsUtil(root.left, curlength, root.data + 1)
		self.longConsUtil(root.right, curlength, root.data + 1)

	def longestConsecutive(self, root):
		if root is None:
			return 0
		global res
		res = 0
		self.longConsUtil(root, 0, root.data)
		if res <= 1:
			return -1
		return res


class Solution:

	def longestConsecutive(self, root):
		self.longest_length = -1
		self.dfs(root, root.data - 1, 0)
		return self.longest_length if self.longest_length >= 2 else -1

	def dfs(self, node, prev_val, curr_length):
		if node:
			if node.data - 1 == prev_val:
				curr_length += 1
				self.longest_length = max(self.longest_length, curr_length)
				self.dfs(node.left, node.data, curr_length)
				self.dfs(node.right, node.data, curr_length)
			else:
				self.dfs(node.left, node.data, 1)
				self.dfs(node.right, node.data, 1)
		return


class Solution:

	def longestConsecutive(self, root):
		self.result = 0
		length = 0

		def func(root, next_value, length):
			if root is None:
				return
			if root.data == next_value:
				length = length + 1
			else:
				length = 1
			self.result = max(self.result, length)
			func(root.left, root.data + 1, length)
			func(root.right, root.data + 1, length)
		func(root, root.data, length)
		if self.result == 1:
			return -1
		return self.result


class Solution:

	def find(self, root, curr_length, prev_data, res):
		if not root:
			return
		if root.data == prev_data:
			curr_length = curr_length + 1
		else:
			curr_length = 1
		res[0] = max(res[0], curr_length)
		self.find(root.left, curr_length, root.data + 1, res)
		self.find(root.right, curr_length, root.data + 1, res)

	def longestConsecutive(self, root):
		res = [0]
		self.find(root, 0, root.data, res)
		if res[0] == 1:
			return -1
		return res[0]


class Solution:

	def longestConsecutive(self, root):
		m = 0

		def solve(a, p, n):
			if a is None:
				return
			if a.data == p + 1:
				n += 1
			else:
				n = 1
			nonlocal m
			m = max(m, n)
			solve(a.left, a.data, n)
			solve(a.right, a.data, n)
		solve(root, -1, 0)
		return m if m > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		if root == None:
			return -1
		ans = [0]

		def getMax(root, ans):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return 1
			left = getMax(root.left, ans)
			right = getMax(root.right, ans)
			leftcur = 1
			rightcur = 1
			if root.left and root.left.data - root.data == 1:
				leftcur += left
			if root.right and root.right.data - root.data == 1:
				rightcur += right
			ans[0] = max(ans[0], leftcur, rightcur)
			return max(leftcur, rightcur)
		getMax(root, ans)
		return ans[0] if ans[0] > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		if root is None:
			return 0
		self.length = 0
		self.longestConsecutiveUtil(root, root.data, 0)
		if self.length > 1:
			return self.length
		return -1

	def longestConsecutiveUtil(self, root, expValue, currentLength):
		if root is None:
			return
		if root.data == expValue:
			currentLength += 1
			self.length = max(self.length, currentLength)
		else:
			currentLength = 1
		self.longestConsecutiveUtil(root.left, root.data + 1, currentLength)
		self.longestConsecutiveUtil(root.right, root.data + 1, currentLength)


class Solution:

	def longestConsecutive(self, root):
		res = [0]
		if root is None:
			return 0
		self.utility(root, res, 0, root.data)
		if res[0] == 1:
			return -1
		return res[0]

	def utility(self, root, res, curLength, expected):
		if root is None:
			return
		if root.data == expected:
			curLength += 1
		else:
			curLength = 1
		res[0] = max(res[0], curLength)
		self.utility(root.left, res, curLength, root.data + 1)
		self.utility(root.right, res, curLength, root.data + 1)


class Solution:

	def longestConsecutive(self, root):
		res = 0

		def solve(root, count, target):
			nonlocal res
			if root == None:
				return
			elif root.data == target:
				count += 1
			else:
				count = 1
			res = max(res, count)
			solve(root.left, count, root.data + 1)
			solve(root.right, count, root.data + 1)
		solve(root, 0, 0)
		return res if res != 1 else -1


def traversal(root, pdata, curr, ans):
	if root:
		if pdata == root.data:
			curr += 1
		else:
			curr = 1
		ans[0] = max(ans[0], curr)
		traversal(root.left, root.data + 1, curr, ans)
		traversal(root.right, root.data + 1, curr, ans)

class Solution:

	def longestConsecutive(self, root):
		ans = [0]
		traversal(root, -1, 1, ans)
		if ans[0] > 1:
			return ans[0]
		else:
			return -1


class Solution:

	def longestConsecutive(self, root):
		c = 0

		def pre(a, x, i):
			if a is None:
				return
			if a.data == x + 1:
				i += 1
			else:
				i = 1
			nonlocal c
			c = max(c, i)
			pre(a.left, a.data, i)
			pre(a.right, a.data, i)
		pre(root, root.data - 1, 0)
		return c if c > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		maxlen = 0

		def dfs(root, c=0):
			nonlocal maxlen
			if not root.left and (not root.right):
				maxlen = max(maxlen, c)
				return
			if root.left:
				if root.left.data == root.data + 1:
					dfs(root.left, c + 1)
				else:
					maxlen = max(maxlen, c)
					dfs(root.left, 0)
			if root.right:
				if root.right.data == root.data + 1:
					dfs(root.right, c + 1)
				else:
					maxlen = max(maxlen, c)
					dfs(root.right, 0)
		dfs(root, 0)
		if maxlen == 0:
			return -1
		else:
			return maxlen + 1


class Solution:

	def longestConsecutive(self, root):
		if not root:
			return -1
		if not root.left and (not root.right):
			return -1
		self.max_len = -1
		self.seq(root.left, root.data, 1)
		self.seq(root.right, root.data, 1)
		return self.max_len

	def seq(self, root, num, l):
		if not root:
			return
		if root.data == num + 1:
			l += 1
		else:
			l = 1
		if l > 1:
			self.max_len = max(self.max_len, l)
		if root.left:
			self.seq(root.left, root.data, l)
		if root.right:
			self.seq(root.right, root.data, l)


from math import inf

class Solution:

	def longestConsecutive(self, root):
		max_len = [1]

		def rec(root, curr_len, expected):
			if not root:
				return
			if root.data == expected:
				curr_len += 1
			else:
				curr_len = 1
			max_len[0] = max(max_len[0], curr_len)
			rec(root.left, curr_len, root.data + 1)
			rec(root.right, curr_len, root.data + 1)
		rec(root, 0, root.data)
		return max_len[0] if max_len[0] > 1 else -1


from math import inf

class Solution:

	def longestConsecutive(self, root):
		max_len = [1]

		def rec(root):
			if not root:
				return [0, inf]
			if not root.left and (not root.right):
				return (1, root.data)
			(l_len, l_val) = rec(root.left)
			(r_len, r_val) = rec(root.right)
			if l_val == r_val:
				if l_val - root.data == 1:
					curr_max_len = max(l_len, r_len) + 1
					max_len[0] = max(max_len[0], curr_max_len)
					return (curr_max_len, root.data)
				else:
					return (1, root.data)
			if l_val - root.data == 1:
				max_len[0] = max(max_len[0], l_len + 1)
				return (l_len + 1, root.data)
			if r_val - root.data == 1:
				max_len[0] = max(max_len[0], r_len + 1)
				return (r_len + 1, root.data)
			return (1, root.data)
		rec(root)
		return max_len[0] if max_len[0] > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		res = 0

		def traverse(root):
			nonlocal res
			cnt = 1
			if not root:
				return 0
			l = traverse(root.left)
			r = traverse(root.right)
			if root.left and root.data + 1 == root.left.data:
				cnt = max(cnt, l + 1)
			if root.right and root.data + 1 == root.right.data:
				cnt = max(cnt, r + 1)
			res = max(res, cnt)
			return cnt
		traverse(root)
		return res if res > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		res = 0

		def count(node):
			nonlocal res
			cur = 1
			if node is None:
				return 0
			left = count(node.left)
			right = count(node.right)
			if node.left and node.data + 1 == node.left.data:
				cur = max(cur, left + 1)
			if node.right and node.data + 1 == node.right.data:
				cur = max(cur, right + 1)
			res = max(res, cur)
			return cur
		count(root)
		return res if res > 1 else -1


class Solution:

	def findLongestConsecutivePathLenght(self, current_node, current_length, expected_val, res):
		if current_node == None:
			return
		elif current_node.data == expected_val:
			current_length += 1
		else:
			current_length = 1
		res[0] = max(res[0], current_length)
		self.findLongestConsecutivePathLenght(current_node.left, current_length, current_node.data + 1, res)
		self.findLongestConsecutivePathLenght(current_node.right, current_length, current_node.data + 1, res)

	def longestConsecutive(self, root):
		if root == None:
			return -1
		res = [0]
		self.findLongestConsecutivePathLenght(root, 0, root.data, res)
		if res[0] == 1:
			return -1
		return res[0]


class Solution:
	count = 0

	def longestConsecutive(self, root):
		if root is None:
			return 0
		self.count = 0
		self.isUpdated = False
		self.dfs(root, -3, 0)
		if self.isUpdated == True:
			return self.count
		return -1

	def dfs(self, root, prev, curr_len):
		if root:
			if root.data - 1 == prev:
				curr_len += 1
				self.isUpdated = True
				self.count = max(curr_len, self.count)
				self.dfs(root.left, root.data, curr_len)
				self.dfs(root.right, root.data, curr_len)
			else:
				self.dfs(root.left, root.data, 1)
				self.dfs(root.right, root.data, 1)


class Solution:

	def longestConsecutive(self, root):
		ans = 0

		def solve(root):
			nonlocal ans
			if root:
				left = solve(root.left)
				right = solve(root.right)
				ans = max([ans, left, right])
				if root.left and root.left.data == root.data + 1 and root.right and (root.right.data == root.data + 1):
					temp = max(left, right) + 1
				elif root.left and root.left.data == root.data + 1:
					temp = left + 1
				elif root.right and root.right.data == root.data + 1:
					temp = right + 1
				else:
					temp = 1
				ans = max(ans, temp)
				return temp
			return 0
		solve(root)
		if ans <= 1:
			return -1
		return ans


class Solution:

	def longestConsecutive(self, root):

		def longest(root, current_length, exp):
			if root is None:
				return
			if root.data == exp:
				current_length += 1
			else:
				current_length = 1
			global res
			res = max(res, current_length)
			longest(root.left, current_length, root.data + 1)
			longest(root.right, current_length, root.data + 1)
		if root is None:
			return 0
		global res
		res = 0
		longest(root, 0, root.data)
		if res <= 1:
			return -1
		return res


class Solution:

	def longestConsecutive(self, root):
		m = -1

		def lc(root, cm):
			nonlocal m
			if root.right:
				if root.right.data == root.data + 1:
					if cm + 1 > m:
						m = cm + 1
					lc(root.right, cm + 1)
				else:
					lc(root.right, 1)
			if root.left:
				if root.left.data == root.data + 1:
					if cm + 1 > m:
						m = cm + 1
					lc(root.left, cm + 1)
				else:
					lc(root.left, 1)
		lc(root, 1)
		return m


class Solution:

	def longestConsecutive(self, root):
		self.maxLength = 1

		def recursive(node, length):
			if node.left:
				if node.left.data - 1 == node.data:
					self.maxLength = max(self.maxLength, length + 1)
					recursive(node.left, length + 1)
				else:
					recursive(node.left, 1)
			if node.right:
				if node.right.data - 1 == node.data:
					self.maxLength = max(self.maxLength, length + 1)
					recursive(node.right, length + 1)
				else:
					recursive(node.right, 1)
		recursive(root, 1)
		return -1 if self.maxLength == 1 else self.maxLength


class Solution:

	def longestConsecutive(self, root):

		def check(root, exp, maxi):
			if root is None:
				return
			if exp == root.data:
				maxi += 1
			else:
				maxi = 1
			global res
			res = max(res, maxi)
			check(root.left, root.data + 1, maxi)
			check(root.right, root.data + 1, maxi)
		if root is None:
			return 0
		global res
		res = 0
		check(root, root.data, 0)
		if res > 1:
			return res
		return -1


class Solution:

	def longestConsecutive(self, root):

		def solve(root, m, c):
			if not root:
				return c
			(l, r, lr) = (0, 0, 0)
			if root.data == m + 1:
				l = solve(root.left, root.data, c + 1)
				r = solve(root.right, root.data, c + 1)
			else:
				lr = max(solve(root.left, root.data, 1), solve(root.right, root.data, 1))
			return max(l, r, lr, c)
		ans = solve(root, root.data, 1)
		return ans if ans > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		ans = -1

		def find(root, l):
			nonlocal ans
			l += 1
			if l > ans:
				ans = l
			if root.left:
				if root.left.data == root.data + 1:
					find(root.left, l)
				else:
					find(root.left, 0)
			if root.right:
				if root.right.data == root.data + 1:
					find(root.right, l)
				else:
					find(root.right, 0)
		if root is None:
			return ans
		find(root, 0)
		if ans < 2:
			return -1
		return ans


import sys
sys.setrecursionlimit(50000)
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

class Solution:

	def longestConsecutive(self, root):

		def check(root, exp, maxi):
			if root is None:
				return
			if exp == root.data:
				maxi += 1
			else:
				maxi = 1
			global res
			res = max(res, maxi)
			check(root.left, root.data + 1, maxi)
			check(root.right, root.data + 1, maxi)
		if root is None:
			return 0
		global res
		res = 0
		check(root, root.data, 0)
		if res <= 1:
			return -1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(Solution().longestConsecutive(root))


import sys
sys.setrecursionlimit(50000)
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

class Solution:

	def longestConsecutive(self, root):
		self.maxCount = 1

		def isConsec(node, parent, count):
			if count > self.maxCount:
				self.maxCount = count
			if node is None:
				return
			if parent and node.data == parent.data + 1:
				count += 1
			else:
				count = 1
			isConsec(node.left, node, count)
			isConsec(node.right, node, count)
		isConsec(root, None, 0)
		return -1 if self.maxCount == 1 else self.maxCount
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(Solution().longestConsecutive(root))


import sys
sys.setrecursionlimit(50000)
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

class Solution:

	def longestConsecutive(self, root):

		def dfs(node):
			if not node:
				return 0
			inr = 1
			if node.left:
				left = dfs(node.left)
				if node.left.data - node.data == 1:
					inr = left + 1
			if node.right:
				right = dfs(node.right)
				if node.right.data - node.data == 1:
					inr = max(inr, right + 1)
			self.longest = max(self.longest, inr)
			return inr
		self.longest = 0
		dfs(root)
		return self.longest if self.longest > 1 else -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(Solution().longestConsecutive(root))


class Solution:

	def longestConsecutive(self, root):
		if not root:
			return -1
		if not root.left and (not root.right):
			return -1
		maxi = [0]
		length = 0
		self.lcUtil(root, root.data, maxi, length)
		if maxi[0] == 0:
			return -1
		return maxi[0]

	def lcUtil(self, root, prev, maxi, length):
		if not root:
			return
		if root.data == prev + 1:
			maxi[0] = max(maxi[0], length)
		else:
			length = 1
		length += 1
		self.lcUtil(root.left, root.data, maxi, length)
		self.lcUtil(root.right, root.data, maxi, length)


class Solution:

	def longestConsecutive(self, root):
		if root.left is None and root.right is None:
			return 1
		globalMax = [0]

		def compute(root, nodeCount):
			if root is None:
				globalMax[0] = max(globalMax[0], nodeCount)
				return
			a = 0
			if root.left:
				if root.data + 1 == root.left.data:
					compute(root.left, nodeCount + 1)
				else:
					globalMax[0] = max(globalMax[0], nodeCount)
					compute(root.left, 1)
			b = 0
			if root.right:
				if root.data + 1 == root.right.data:
					compute(root.right, nodeCount + 1)
				else:
					globalMax[0] = max(globalMax[0], nodeCount)
					compute(root.right, 1)
			globalMax[0] = max(globalMax[0], nodeCount)
		compute(root, 1)
		if globalMax[0] == 1:
			return -1
		else:
			return globalMax[0]


class Solution:

	def longestConsecutive(self, root):
		m = 1

		def post(a, x, c):
			nonlocal m
			if not a:
				return 0
			if a.data == x:
				c += 1
			else:
				c = 1
			m = max(m, c)
			post(a.left, a.data + 1, c)
			post(a.right, a.data + 1, c)
		post(root, 0, 1)
		return m if m > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		dic = {}
		ans = [0]

		def helper(root, cur, exp):
			if not root:
				return
			if root.data == exp:
				cur += 1
			else:
				cur = 1
			ans[0] = max(ans[0], cur)
			helper(root.left, cur, root.data + 1)
			helper(root.right, cur, root.data + 1)
		helper(root, 0, root.data)
		return ans[0] if ans[0] != 1 else -1


class Solution:

	def longestConsecutiveUtil(self, root, res, expected, curr):
		if root is None:
			return
		if root.data == expected:
			curr += 1
		else:
			curr = 1
		res[0] = max(res[0], curr)
		self.longestConsecutiveUtil(root.left, res, root.data + 1, curr)
		self.longestConsecutiveUtil(root.right, res, root.data + 1, curr)

	def longestConsecutive(self, root):
		if root is None:
			return -1
		res = [0]
		self.longestConsecutiveUtil(root, res, -1, 0)
		return -1 if res[0] == 1 else res[0]


import sys

class Solution:
	ans = -1

	def pre(self, root):
		if root is None:
			return [sys.maxsize, 0]
		len = 1
		y = self.pre(root.right)
		x = self.pre(root.left)
		if x[0] != sys.maxsize:
			if x[0] - root.data == 1:
				if 1 + x[1] > len:
					len = 1 + x[1]
		if y[0] != sys.maxsize:
			if y[0] - root.data == 1:
				if 1 + y[1] > len:
					len = 1 + y[1]
		if len > self.ans:
			self.ans = len
		return [root.data, len]

	def longestConsecutive(self, root):
		self.pre(root)
		return self.ans if self.ans > 1 else -1


class Solution:

	def dfs(self, node):
		if not node:
			return 0
		res = 1
		(l, r) = (self.dfs(node.left), self.dfs(node.right))
		if node.left and node.left.data == node.data + 1:
			res = max(res, l + 1)
		if node.right and node.right.data == node.data + 1:
			res = max(res, r + 1)
		self.ans = max(self.ans, res)
		return res

	def longestConsecutive(self, root):
		self.ans = 0
		self.dfs(root)
		return -1 if self.ans == 1 else self.ans


class Solution:

	def longConsecutiveUtil(self, root, size, value, ans):
		if root == None:
			return
		if root.data == value:
			size += 1
		else:
			size = 1
		ans[0] = max(ans[0], size)
		self.longConsecutiveUtil(root.left, size, root.data + 1, ans)
		self.longConsecutiveUtil(root.right, size, root.data + 1, ans)

	def longestConsecutive(self, root):
		if root == None:
			return 0
		ans = [0]
		self.longConsecutiveUtil(root, 0, root.data, ans)
		if ans[0] < 2:
			return -1
		return ans[0]


class Solution:

	def longestConsecutive(self, root):
		self.res = 0

		def solve(root, length):
			self.res = max(self.res, length)
			if not root:
				return
			if root.left:
				if root.left.data == root.data + 1:
					solve(root.left, length + 1)
				else:
					solve(root.left, 0)
			if root.right:
				if root.right.data == root.data + 1:
					solve(root.right, length + 1)
				else:
					solve(root.right, 0)
		solve(root, 0)
		return self.res + 1 if self.res > 0 else -1


class Solution:

	def path(self, root, val, max_val, count, res):
		if not root:
			return None
		if root.data == val:
			count += 1
		else:
			count = 1
		res[0] = max(res[0], count)
		self.path(root.left, root.data + 1, max_val, count, res)
		self.path(root.right, root.data + 1, max_val, count, res)

	def longestConsecutive(self, root):
		max_val = 0
		res = [0]
		self.path(root, root.data, max_val, 0, res)
		if res[0] >= 2:
			return res[0]
		else:
			return -1


class Solution:

	def findLongestConsecutive(self, root, curLen, val, res):
		if root is None:
			return
		if root.data == val:
			curLen += 1
		else:
			curLen = 1
		res[0] = max(res[0], curLen)
		self.findLongestConsecutive(root.left, curLen, root.data + 1, res)
		self.findLongestConsecutive(root.right, curLen, root.data + 1, res)

	def longestConsecutive(self, root):
		if root is None:
			return
		res = [0]
		self.findLongestConsecutive(root, 0, root.data, res)
		if res[0] <= 1:
			return -1
		return res[0]


class Solution:

	def longestConsecutive(self, root):

		def dfs(node, target):
			nonlocal maxlen
			if not node:
				return 0
			left_cnt = dfs(node.left, node.data + 1)
			right_cnt = dfs(node.right, node.data + 1)
			res = max(left_cnt, right_cnt) + 1
			maxlen = max(maxlen, res)
			if node.data == target:
				return res
			else:
				return 0
		if not root:
			return 0
		maxlen = 0
		dfs(root, root.data)
		return maxlen if maxlen > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		res = [0]

		def dfs(root, prev, currLen):
			if not root:
				return 0
			if root.data - 1 == prev.data:
				currLen += 1
			else:
				currLen = 1
			res[0] = max(res[0], currLen)
			dfs(root.left, root, currLen)
			dfs(root.right, root, currLen)
		dfs(root, root, 0)
		return res[0] if res[0] > 1 else -1


class Solution:

	def longestConsecutive(self, root):
		if root is None:
			return 0
		res = [0]
		self.longestConsecutiveUtil(root, res, root.data, 0)
		if res[0] <= 1:
			return -1
		return res[0]

	def longestConsecutiveUtil(self, root, result, exp, length):
		if root is None:
			return
		if root.data == exp:
			length += 1
		else:
			length = 1
		result[0] = max(result[0], length)
		self.longestConsecutiveUtil(root.left, result, root.data + 1, length)
		self.longestConsecutiveUtil(root.right, result, root.data + 1, length)


class Solution:

	def helper(self, root, prev, res, curr):
		if not root:
			return
		if root.data == prev:
			curr += 1
		else:
			curr = 1
		self.res = max(self.res, curr)
		self.helper(root.left, root.data + 1, res, curr)
		self.helper(root.right, root.data + 1, res, curr)

	def longestConsecutive(self, root):
		prev = 0
		self.res = -1
		self.helper(root, root.data, self.res, 0)
		if self.res <= 1:
			return -1
		return self.res


class Solution:

	def __init__(self):
		self.m = 0

	def longestConsecutive(self, root):

		def lcm(root, p, l):
			if root == None:
				return
			if root.data == p + 1:
				l += 1
				self.m = max(self.m, l)
			else:
				l = 1
			lcm(root.left, root.data, l)
			lcm(root.right, root.data, l)
		lcm(root, float('-inf'), 1)
		if self.m == 0:
			return -1
		else:
			return self.m


def util(root, currLength, expected):
	if root == None:
		return
	if root.data == expected:
		currLength += 1
	else:
		currLength = 1
	global maxlen
	maxlen = max(maxlen, currLength)
	util(root.left, currLength, root.data + 1)
	util(root.right, currLength, root.data + 1)

class Solution:

	def longestConsecutive(self, root):
		global maxlen
		maxlen = 0
		util(root, 0, root.data)
		if maxlen <= 1:
			return -1
		return maxlen


class Solution:

	def longestConsecutive(self, root):
		if not root:
			return 0
		maxlength = [0]

		def dfs(node, pvalue, lengthsofar):
			if node.data == pvalue + 1:
				lengthsofar += 1
			else:
				lengthsofar = 1
			if lengthsofar > maxlength[0]:
				maxlength[0] = lengthsofar
			if node.left is None and node.right is None:
				pass
			if node.left:
				dfs(node.left, node.data, lengthsofar)
			if node.right:
				dfs(node.right, node.data, lengthsofar)
		dfs(root, root.data, 1)
		if maxlength[0] > 1:
			return maxlength[0]
		return -1


class Solution:

	def longestConsecutive(self, root):
		longest = 0

		def build(root, val, length):
			nonlocal longest
			if not root:
				return
			if val == root.data:
				length += 1
			else:
				length = 1
			longest = max(length, longest)
			build(root.left, root.data + 1, length)
			build(root.right, root.data + 1, length)
		build(root, root.data, 0)
		if longest <= 1:
			return -1
		return longest


class Solution:

	def longestConsecutive(self, root):
		result = [-1]
		result_so_far = 0

		def dfs(node, p_val, result_so_far):
			if node.data == p_val + 1:
				result_so_far += 1
				result[0] = max(result[0], result_so_far)
			else:
				result_so_far = 1
			if node.left:
				dfs(node.left, node.data, result_so_far)
			if node.right:
				dfs(node.right, node.data, result_so_far)
		dfs(root, root.data, 1)
		return result[0]


class Solution:

	def __init__(self):
		self.result = -1

	def lcUtil(self, root):
		temp = 1
		if root.left:
			l = self.lcUtil(root.left)
			if root.data + 1 == root.left.data:
				temp = max(temp, 1 + l)
		if root.right:
			r = self.lcUtil(root.right)
			if root.data + 1 == root.right.data:
				temp = max(temp, 1 + r)
		self.result = max(self.result, temp)
		return temp

	def longestConsecutive(self, root):
		if root is not None:
			self.lcUtil(root)
		if self.result == -1 or self.result == 1:
			return -1
		return self.result


class Solution:

	def longestConsecutive(self, root):
		res = [-1]

		def util(root, curlen, expected):
			if not root:
				return
			if root.data == expected:
				curlen += 1
			else:
				curlen = 1
			res[0] = max(res[0], curlen)
			util(root.left, curlen, root.data + 1)
			util(root.right, curlen, root.data + 1)
		util(root, 0, root.data)
		return res[0] if res[0] > 1 else -1


def dfs(root, d, ans, curlen):
	if root is None:
		return
	if root.data == d:
		curlen += 1
	else:
		curlen = 1
	ans[0] = max(ans[0], curlen)
	dfs(root.left, root.data + 1, ans, curlen)
	dfs(root.right, root.data + 1, ans, curlen)

class Solution:

	def longestConsecutive(self, root):
		ans = [0]
		dfs(root, root.data, ans, 0)
		if ans[0] == 1:
			return -1
		return ans[0]


class Solution:

	def longestConsecutive(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return -1
		maxi = [0]
		length = 0
		self.longestConsecutiveUtil(root, root.data, length, maxi)
		if maxi[0] == 0:
			return -1
		return maxi[0]

	def longestConsecutiveUtil(self, root, prev, length, maxi):
		if root == None:
			return
		if root.data == prev + 1:
			maxi[0] = max(maxi[0], length)
		else:
			length = 1
		length += 1
		self.longestConsecutiveUtil(root.left, root.data, length, maxi)
		self.longestConsecutiveUtil(root.right, root.data, length, maxi)


class Solution:

	def longestConsecutive(self, root):

		def helper(node):
			if not node:
				return (0, 0)
			x = helper(node.left)
			y = helper(node.right)
			excluding = max(x[1], y[1], x[0], y[0])
			including = 1
			subcall = 0
			if node.left and node.left.data == node.data + 1:
				subcall = max(subcall, x[0])
			if node.right and node.right.data == node.data + 1:
				subcall = max(subcall, y[0])
			including += subcall
			return (including, excluding)
		r = helper(root)
		r = max(r[0], r[1])
		return r if r != 1 else -1


class Solution:

	def longestConsecutive(self, root):
		res = self.helper(root, 0, 0)
		if res == 1:
			return -1
		else:
			return res

	def helper(self, root, expected, length):
		if root is None:
			return length
		curlength = 1
		if root.data == expected:
			curlength = length + 1
		return max([self.helper(root.right, root.data + 1, curlength), self.helper(root.left, root.data + 1, curlength), curlength])


class Solution:

	def helper(self, root, parentValue, pathLength, maxLength):
		if root == None:
			return
		if parentValue + 1 == root.data:
			pathLength += 1
			maxLength[0] = max(maxLength[0], pathLength)
		else:
			pathLength = 0
		self.helper(root.left, root.data, pathLength, maxLength)
		self.helper(root.right, root.data, pathLength, maxLength)

	def longestConsecutive(self, root):
		maxLength = [0]
		self.helper(root, -99999, 0, maxLength)
		if maxLength[0] == 0:
			return -1
		else:
			return maxLength[0] + 1


class Solution:

	def longestConsecutive(self, root):
		ls = [1]
		self.dfs(root, 1, ls)
		if ls[0] == 1:
			return -1
		else:
			return ls[0]

	def dfs(self, root, pas, ls):
		if root is None:
			return
		if pas > ls[0]:
			ls[0] = pas
		if root.left:
			if root.data + 1 == root.left.data:
				self.dfs(root.left, pas + 1, ls)
			else:
				self.dfs(root.left, 1, ls)
		if root.right:
			if root.data + 1 == root.right.data:
				self.dfs(root.right, pas + 1, ls)
			else:
				self.dfs(root.right, 1, ls)


from collections import deque

class Solution:

	def longestConsecutive(self, root):
		stack = deque([(root, 10 ** 9, 1)])
		max_len = 0
		while stack:
			(node, prev_val, cur_len) = stack.pop()
			if node.data == prev_val + 1:
				cur_len += 1
				if cur_len > max_len:
					max_len = cur_len
			else:
				cur_len = 1
			if node.left:
				stack.append((node.left, node.data, cur_len))
			if node.right:
				stack.append((node.right, node.data, cur_len))
		return max_len if max_len >= 2 else -1


class Solution:
	ans = 0

	def util(self, root, exp, cur):
		if root is None:
			return 0
		if root.data == exp:
			cur += 1
		else:
			cur = 1
		self.ans = max(self.ans, cur)
		self.util(root.left, root.data + 1, cur)
		self.util(root.right, root.data + 1, cur)

	def longestConsecutive(self, root):
		if root is None:
			return 0
		self.util(root, root.data, 0)
		if self.ans == 1:
			return -1
		return self.ans


class Solution:

	def longestConsecutive(self, root):
		self.answer = 0
		self.solution(root, 1)
		if self.answer == 1:
			return -1
		return self.answer

	def solution(self, startnode, count):
		self.answer = max(self.answer, count)
		if startnode == None:
			return
		if startnode.left:
			if startnode.left.data == startnode.data + 1:
				self.solution(startnode.left, count + 1)
			else:
				self.solution(startnode.left, 1)
		if startnode.right:
			if startnode.right.data == startnode.data + 1:
				self.solution(startnode.right, count + 1)
			else:
				self.solution(startnode.right, 1)


class Solution:
	res = 0

	def solve(self, root, expected, curLen):
		if not root:
			return
		if root.data == expected:
			curLen += 1
		else:
			curLen = 1
		self.res = max(self.res, curLen)
		self.solve(root.left, root.data + 1, curLen)
		self.solve(root.right, root.data + 1, curLen)

	def longestConsecutive(self, root):
		if not root:
			return
		self.solve(root, root.data, 0)
		if self.res < 2:
			return -1
		return self.res


class Solution:

	def longestConsecutive(self, root):
		if root == None:
			return -1

		def solve(node, parent_value, res, curlength):
			if node == None:
				return
			if node.data == parent_value + 1:
				curlength += 1
			else:
				curlength = 1
			res[0] = max(curlength, res[0])
			solve(node.left, node.data, res, curlength)
			solve(node.right, node.data, res, curlength)
		res = [-1]
		solve(root, root.data, res, 1)
		if res[0] == 1:
			return -1
		return res[0]


class Solution:

	def longestConsecutive(self, root):
		self.m_len = 0

		def traverse(root):
			if not root:
				return (-1, 0)
			else:
				(l_val, l_len) = traverse(root.left)
				(r_val, r_len) = traverse(root.right)
				my_len = 1
				if l_len > 0 and l_val == root.data + 1:
					my_len = my_len if my_len > l_len + 1 else l_len + 1
				if r_len > 0 and r_val == root.data + 1:
					my_len = my_len if my_len > r_len + 1 else r_len + 1
				if my_len > self.m_len:
					self.m_len = my_len
				return (root.data, my_len)
		traverse(root)
		return -1 if self.m_len < 2 else self.m_len


class Solution:

	def longestConsecutive(self, root):
		max_count = 0

		def traverse(node, prev, count):
			nonlocal max_count
			if node == None:
				return
			if prev:
				if node.data == prev.data + 1:
					count += 1
					max_count = max(max_count, count)
				else:
					max_count = max(max_count, count)
					count = 1
			traverse(node.left, node, count)
			traverse(node.right, node, count)
		traverse(root, None, 1)
		if max_count < 2:
			return -1
		return max_count


class Solution:

	def longestConsecutive(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		maxi = [-1]
		ans = self.getLongestConsec(root, root.data, maxi, 0)
		if ans[0] == -1:
			return -1
		return ans[0]

	def getLongestConsec(self, root, prev, maxi, leng):
		if root == None:
			return
		if root.data == prev + 1:
			maxi[0] = max(maxi[0], leng)
		else:
			leng = 1
		leng += 1
		self.getLongestConsec(root.left, root.data, maxi, leng)
		self.getLongestConsec(root.right, root.data, maxi, leng)
		return maxi


class Solution:

	def __init__(self):
		self.result = 0

	def soln(self, root):
		if root is None:
			return self.result
		l = self.soln(root.left)
		r = self.soln(root.right)
		right = 1
		left = 1
		if root.left:
			if root.data + 1 == root.left.data:
				left = l + left
		if root.right:
			if root.data + 1 == root.right.data:
				right = r + right
		self.result = max(self.result, max(left, right))
		return max(left, right)

	def longestConsecutive(self, root):
		self.soln(root)
		if self.result < 2:
			return -1
		return self.result


class Solution:

	def longestConsecutive(self, root):
		if root is None:
			return -1
		ans = self.__longest_consecutive(root, root.data - 1, 0)
		if ans < 2:
			return -1
		return ans

	def __longest_consecutive(self, root, prev_val, prev_len):
		if root is None:
			return prev_len
		curr_val = root.data
		if curr_val == prev_val + 1:
			return max(self.__longest_consecutive(root.left, curr_val, prev_len + 1), self.__longest_consecutive(root.right, curr_val, prev_len + 1))
		newPathLen = max(self.__longest_consecutive(root.left, curr_val, 1), self.__longest_consecutive(root.right, curr_val, 1))
		return max(prev_len, newPathLen)


import math

class Solution:

	def longestConsecutive(self, root):
		self._max = 0
		self.find(root, root.data, 1)
		if self._max == 1:
			return -1
		return self._max

	def findSol(self, root, h):
		if not root:
			return
		if not root.left and (not root.right):
			self._max = max(self._max, h)
			return
		if root.left and root.left.data == root.data + 1:
			self.findSol(root.left, h + 1)
		else:
			self.findSol(root.left, 1)
		if root.right and root.right.data == root.data + 1:
			self.findSol(root.right, h + 1)
		else:
			self.findSol(root.right, 1)
		return

	def find(self, root, val, h):
		if not root:
			return
		if root.data == val + 1:
			h = h + 1
		else:
			h = 1
		self._max = max(self._max, h)
		self.find(root.left, root.data, h)
		self.find(root.right, root.data, h)


from typing import Optional

class Solution:

	def __init__(self):
		self.mx = -1

	def longestConsecutive(self, root: Optional[Node]) -> int:
		if not root:
			return 0

		def rec(node, pval, k):
			if k > 1:
				self.mx = max(self.mx, k)
			if not node:
				return
			if node:
				if node.data == pval + 1:
					k += 1
					rec(node.left, node.data, k)
					rec(node.right, node.data, k)
					k -= 1
				else:
					rec(node.left, node.data, 1)
					rec(node.right, node.data, 1)
		rec(root, -1, 1)
		return self.mx


from collections import deque

class Solution:

	def longestConsecutive(self, root):
		res = -1
		queue = deque([[1, root]])
		while queue:
			(l, p) = queue.popleft()
			if l >= 2:
				res = max(res, l)
			for q in [p.left, p.right]:
				if q:
					if q.data == p.data + 1:
						queue.append([l + 1, q])
					else:
						queue.append([1, q])
		return res


class Solution:

	def longestConsecutive(self, root):
		res = -1
		stack = [(1, root)]
		while stack:
			(l, p) = stack.pop()
			if l >= 2:
				res = max(res, l)
			for q in [p.left, p.right]:
				if q:
					if q.data == p.data + 1:
						stack.append([l + 1, q])
					else:
						stack.append([1, q])
		return res


class Solution:

	def longestConsecutive(self, root):
		if not root:
			return 0
		count = 0
		ret = self.longestConsecutiveHelper(root, root.data, count)
		if ret == 1:
			return -1
		return ret

	def longestConsecutiveHelper(self, root, target, count):
		if not root:
			return 0
		if root.data == target:
			count += 1
		else:
			count = 1
		left = self.longestConsecutiveHelper(root.left, root.data + 1, count)
		right = self.longestConsecutiveHelper(root.right, root.data + 1, count)
		return max(count, max(left, right))


class Solution:

	def longestConsecutive(self, root):
		self.longest = 0

		def dfs(node):
			if not node:
				return 0
			height = 1
			l = dfs(node.left)
			r = dfs(node.right)
			if not node.left or node.left.data != node.data + 1:
				l = 0
			if not node.right or node.right.data != node.data + 1:
				r = 0
			height += max(l, r)
			self.longest = max(self.longest, height)
			return height
		dfs(root)
		if self.longest <= 1:
			return -1
		return self.longest


class Solution:

	def longestConsecutive(self, root):

		def path(root, pathLength, expected):
			if not root:
				return
			if root.data == expected:
				pathLength += 1
			else:
				pathLength = 1
			path.ans = max(path.ans, pathLength)
			path(root.left, pathLength, root.data + 1)
			path(root.right, pathLength, root.data + 1)
		path.ans = 0
		path(root, 0, root.data)
		return path.ans if path.ans > 1 else -1


class Solution:

	def lc(self, root, res, lc, pv):
		if not root:
			return
		if root.data == pv + 1:
			lc += 1
			res[0] = max(res[0], lc)
		else:
			lc = 1
		self.lc(root.left, res, lc, root.data)
		self.lc(root.right, res, lc, root.data)

	def longestConsecutive(self, root):
		if not root:
			return -1
		res = [1]
		self.lc(root, res, 1, root.data)
		if res[0] == 1:
			return -1
		return res[0]


class Solution:

	def longestConsecutive(self, root):
		ans = [0]

		def find(root):
			if not root:
				return 0
			if not root.left and (not root.right):
				return 1
			f = False
			l = find(root.left)
			r = find(root.right)
			lcl = 0
			f = False
			if root.left and root.data + 1 == root.left.data:
				l += 1
				f = True
			if root.right and root.data + 1 == root.right.data:
				r += 1
				f = True
			ans[0] = max(ans[0], l, r)
			if f:
				return max(l, r)
			return 1
		find(root)
		return ans[0] if ans[0] != 1 else -1


class Solution:

	def cal(self, root, exp, curr):
		global res
		if root == None:
			return
		if root.data == exp:
			curr += 1
		else:
			curr = 1
		res = max(res, curr)
		self.cal(root.left, root.data + 1, curr)
		self.cal(root.right, root.data + 1, curr)

	def longestConsecutive(self, root):
		global res
		res = 0
		self.cal(root, root.data, 0)
		if res == 1:
			return -1
		else:
			return res