Given a binary tree and data value of two of its nodes. Find the number of turns needed to reach from one node to another in the given binary tree.
Example 1:
Input:      
Tree = 
           1
        /    \
       2       3
     /  \     /  \
    4    5   6    7                        
   /        / \                        
  8        9   10   
first node = 5
second node = 10
Output: 4
Explanation: 
Turns will be at 2, 1, 3, 6.
Example 2:
Input:      
Tree = 
           1
        /     \
       2        3
     /  \      /  \
    4    5    6    7                        
   /         / \                        
  8         9   10   
first node = 1
second node = 4  
Output: -1
Explanation: No turn is required since 
they are in a straight line.
Your Task:  
You don't need to read input or print anything. Complete the function NumberOFTurns() which takes root node and data value of 2 nodes as input parameters and returns the number of turns required to navigate between them. If the two nodes are in a straight line, ie- the path does not involve any turns, return -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of Tree)
Constraints:
1 ≤ N ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data=val

        self.left=None

        self.right=None

'''



class Solution:

    def NumberOFTurns(self, root, first, second):

        #return the number of turns required to go from first node to second node

Solutions:
class Solution:

	def lowestCommonAncestor(self, root, p, q):
		if not root or root.data == p or root.data == q:
			return root
		left = self.lowestCommonAncestor(root.left, p, q)
		right = self.lowestCommonAncestor(root.right, p, q)
		if not left:
			return right
		elif not right:
			return left
		else:
			return root

	def solve(self, root, count, direction, num, ans):
		if not root:
			return
		if root.data == num:
			ans[0] = count
			return
		self.solve(root.left, count + (direction != 0), 0, num, ans)
		self.solve(root.right, count + (direction != 1), 1, num, ans)

	def NumberOFTurns(self, root, p, q):
		lca = self.lowestCommonAncestor(root, p, q)
		count = 0
		ans = [0]
		self.solve(lca, count, -1, p, ans)
		pans = ans[0] - 1
		ans[0] = 0
		count = 0
		self.solve(lca, count, -1, q, ans)
		qans = ans[0] - 1
		if lca.data == p:
			if qans != 0:
				return qans
			else:
				return -1
		elif lca.data == q:
			if pans != 0:
				return pans
			else:
				return -1
		else:
			return pans + qans + 1


class Solution:

	def NumberOFTurns(self, root, first, second):
		anc = self.LCA(root, first, second)
		fres = ['']
		cres = ''
		self.getlistofturns(anc, first, cres, fres)
		l1 = fres
		fres = ['']
		cres = ''
		self.getlistofturns(anc, second, cres, fres)
		l2 = fres
		c1 = self.countturns(l1[0])
		c2 = self.countturns(l2[0])
		if len(l1[0]) == 0 and len(l2[0]) == 0:
			return 0
		elif len(l1[0]) == 0 and c2 == 0 or (len(l2[0]) == 0 and c1 == 0):
			return 0
		elif len(l1[0]) == 0 and c2 != 0 or (len(l2[0]) == 0 and c1 != 0):
			return c1 + c2
		return c1 + c2 + 1

	def countturns(self, A):
		if len(A) <= 1:
			return 0
		i = 0
		count = 0
		while i < len(A) - 1:
			if A[i] != A[i + 1]:
				count += 1
			i += 1
		return count

	def getlistofturns(self, currentnode, target, cres, fres):
		if fres[0] != '':
			return
		if currentnode is None:
			return
		if currentnode.data == target:
			fres[0] = cres
			return
		self.getlistofturns(currentnode.left, target, cres + 'L', fres)
		self.getlistofturns(currentnode.right, target, cres + 'R', fres)

	def LCA(self, root, first, second):
		if root is None:
			return
		if root.data == first or root.data == second:
			return root
		left_lca = self.LCA(root.left, first, second)
		right_lca = self.LCA(root.right, first, second)
		if left_lca and right_lca:
			return root
		return left_lca if left_lca is not None else right_lca


def lca(root, n1, n2):
	if root == None:
		return None
	if root.data == n1 or root.data == n2:
		return root
	l = lca(root.left, n1, n2)
	r = lca(root.right, n1, n2)
	if l and r:
		return root
	if l:
		return l
	return r

class Solution:

	def NumberOFTurns(self, root, first, second):
		la = lca(root, first, second)
		mx1 = [0] * 1
		mx2 = [0] * 1

		def fun(root, x, t, flag, flag1):
			if root == None:
				return
			if root.data == x:
				if flag:
					mx1[0] = t
				else:
					mx2[0] = t
				return
			if flag1 == None:
				fun(root.left, x, t, flag, True)
				fun(root.right, x, t, flag, False)
			elif flag1:
				fun(root.left, x, t, flag, True)
				fun(root.right, x, t + 1, flag, False)
			else:
				fun(root.left, x, t + 1, flag, True)
				fun(root.right, x, t, flag, False)
		fun(la, first, 0, True, None)
		fun(la, second, 0, False, None)
		if la.data == first or la.data == second:
			return mx1[0] + mx2[0]
		return mx1[0] + mx2[0] + 1


class Solution:

	def getParent(self, root, first, second, parent):
		if root == None:
			return root
		l = self.getParent(root.left, first, second, parent)
		r = self.getParent(root.right, first, second, parent)
		if root.data == first or root.data == second:
			return root
		if l != None and r != None:
			parent[0] = root
			return None
		elif l != None:
			return l
		elif r != None:
			return r
		return None

	def Preorder(self, root, data, cnt, s, count):
		if root == None:
			return
		if root.data == data:
			count[0] += cnt
			return
		if s == 'n' or s == 'r':
			self.Preorder(root.left, data, cnt + 1, 'l', count)
		else:
			self.Preorder(root.left, data, cnt, 'l', count)
		if s == 'n' or s == 'l':
			self.Preorder(root.right, data, cnt + 1, 'r', count)
		else:
			self.Preorder(root.right, data, cnt, 'r', count)

	def NumberOFTurns(self, root, first, second):
		if first == second:
			return -1
		parent = [Node(-1)]
		f = self.getParent(root, first, second, parent)
		if parent[0].data == -1 and f == None:
			return -1
		elif f != None:
			parent[0] = f
		count = [0]
		if f == None:
			self.Preorder(parent[0], first, 0, 'n', count)
			self.Preorder(parent[0], second, 0, 'n', count)
			if count[0] == 0:
				return -1
			return count[0] - 1
		else:
			self.Preorder(parent[0], first, 0, 't', count)
			self.Preorder(parent[0], second, 0, 't', count)
			if count[0] == 0:
				return -1
			return count[0]
		return count[0]


class Solution:

	def findLCA(self, n, a, b):
		if n is None:
			return None
		if n.data == a or n.data == b:
			return n
		l = self.findLCA(n.left, a, b)
		r = self.findLCA(n.right, a, b)
		if l and r:
			return n
		if l:
			return l
		return r

	def count(self, n, prev, target):
		if n is None:
			return -1
		if n.data == target:
			return 0
		val = self.count(n.left, 'l', target)
		if val != -1:
			return val + int(prev == 'r')
		val = self.count(n.right, 'r', target)
		if val != -1:
			return val + int(prev == 'l')
		return -1

	def NumberOFTurns(self, root, n1, n2):
		LCA = self.findLCA(root, n1, n2)
		ret = 0
		if LCA.data == n1:
			ret = self.count(LCA, 'x', n2)
		elif LCA.data == n2:
			ret = self.count(LCA, 'x', n1)
		else:
			ret = self.count(LCA, 'x', n1) + self.count(LCA, 'x', n2) + 1
		return ret


class Solution:

	def NumberOFTurns(self, root, first, second):
		res = ''

		def lca(r, p, q):
			if not r:
				return
			if r.data == q or r.data == p:
				return r
			left = lca(r.left, p, q)
			right = lca(r.right, p, q)
			if left is None:
				return right
			if right is None:
				return left
			return r
		x = lca(root, first, second)

		def height(r, t, s):
			nonlocal res
			if not r:
				return False
			if r.data == t:
				res = s
				return res
			if r.left:
				height(r.left, t, s + 'L')
			if r.right:
				height(r.right, t, s + 'R')
		a = height(x, first, '')
		a = res
		res = ''
		height(x, second, '')
		b = res
		(a1, b1) = (0, 0)
		for i in range(1, len(a)):
			if a[i] != a[i - 1]:
				a1 += 1
		for i in range(1, len(b)):
			if b[i] != b[i - 1]:
				b1 += 1
		if x.data == first:
			return b1
		elif x.data == second:
			return a1
		return a1 + b1 + 1


class Solution:

	def NumberOFTurns(self, root, first, second):

		def find(root, ele):
			if root is None:
				return (False, [])
			if root.data == ele:
				return (True, [(root.data, '$')])
			(foundL, left) = find(root.left, ele)
			(foundR, right) = find(root.right, ele)
			if foundL:
				return (foundL, [(root.data, 'L')] + left)
			if foundR:
				return (foundR, [(root.data, 'R')] + right)
			return (False, [])
		(ans, a) = find(root, first)
		(ans, b) = find(root, second)
		m = min(len(a), len(b))
		i = 0
		while i < m and a[i][0] == b[i][0]:
			i += 1
		idx = max(i, 1)
		turns = 0
		if a and b and (a[idx - 1][1] != b[idx - 1][1]) and (a[idx - 1][1] != '$' and b[idx - 1][1] != '$'):
			turns += 1
		for i in range(idx, len(a)):
			if a[i - 1][1] != a[i][1] and (a[i - 1][1] != '$' and a[i][1] != '$'):
				turns += 1
		for i in range(idx, len(b)):
			if b[i - 1][1] != b[i][1] and (b[i - 1][1] != '$' and b[i][1] != '$'):
				turns += 1
		return turns


class Solution:

	def mod(self, way):
		ans = 0
		curr = None
		for x in way:
			if curr == None:
				curr = x
			if x != curr:
				ans += 1
				curr = x
		return ans

	def __init__(self):
		self.get = [False, False]

	def travell(self, root, f, s, di=None, pathTill=[]):
		if root == None:
			return ([], [])
		if root.data == f:
			self.get[0] = True
			w1 = self.travell(root.left, f, s, 'l', [*pathTill, 'l'])
			w2 = self.travell(root.right, f, s, 'r', [*pathTill, 'r'])
			return (pathTill, w1[1] + w2[1])
		if root.data == s:
			self.get[1] = True
			w1 = self.travell(root.left, f, s, 'l', [*pathTill, 'l'])
			w2 = self.travell(root.right, f, s, 'r', [*pathTill, 'r'])
			return (w1[0] + w2[0], pathTill)
		w1 = self.travell(root.left, f, s, 'l', [*pathTill, 'l'])
		w2 = self.travell(root.right, f, s, 'r', [*pathTill, 'r'])
		return (w1[0] + w2[0], w1[1] + w2[1])

	def NumberOFTurns(self, root, first, second):
		(fw, sw) = self.travell(root, first, second)
		if self.get != [True, True]:
			return -1
		while fw and sw:
			if fw[0] == sw[0]:
				del fw[0], sw[0]
			else:
				break
		ans = self.mod(fw) + self.mod(sw)
		if fw and sw:
			return ans + 1
		return ans


class Solution:

	def findLCA(self, root, first, second):
		if not root:
			return root
		if root.data == first or second == root.data:
			return root
		left = self.findLCA(root.left, first, second)
		right = self.findLCA(root.right, first, second)
		if left is None:
			return right
		elif right is None:
			return left
		else:
			return root

	def getPath(self, lca, nodeVal, path, direction):
		if not lca:
			return False
		path.append(direction)
		if lca.data == nodeVal:
			return True
		if self.getPath(lca.left, nodeVal, path, 0) or self.getPath(lca.right, nodeVal, path, 1):
			return True
		path.pop(-1)
		return False

	def NumberOFTurns(self, root, first, second):
		lca = self.findLCA(root, first, second)
		path1 = []
		self.getPath(lca, first, path1, -1)
		path2 = []
		self.getPath(lca, second, path2, -1)
		path1.pop(0)
		path2.pop(0)
		path1 = path1[::-1]
		path1.extend(path2)
		(l, r, turns) = (0, 1, 0)
		while r < len(path1):
			if path1[l] != path1[r]:
				turns += 1
			l += 1
			r += 1
		return turns


class Solution:

	def findPath(self, root, parent, path, n):
		if root is None:
			return False
		path.append([root.data, parent])
		if root.data == n:
			return True
		if root.left != None and self.findPath(root.left, root, path, n) or (root.right != None and self.findPath(root.right, root, path, n)):
			return True
		path.pop()
		return False

	def FindLCA(self, root, first, second, path1, path2):
		if not self.findPath(root, None, path1, first) or not self.findPath(root, None, path2, second):
			return -1
		i = 0
		while i < len(path1) and i < len(path2):
			if path1[i][0] != path2[i][0]:
				break
			i += 1
		return path1[i - 1]

	def getTurns(self, __path):
		turns = -1
		plen = len(__path)
		if plen > 1:
			turns = 0
			direction = '?'
			for i in range(plen):
				p = __path[i][1]
				if p:
					if p.left and p.left.data == __path[i][0]:
						if direction == '?':
							direction = 'L'
						elif direction != 'L':
							turns += 1
							direction = 'L'
					elif p.right and p.right.data == __path[i][0]:
						if direction == '?':
							direction = 'R'
						elif direction != 'R':
							turns += 1
							direction = 'R'
				elif i < plen - 1:
					turns += 1
					if direction == 'R':
						direction = 'L'
					else:
						direction = 'R'
		return turns

	def NumberOFTurns(self, root, first, second):
		path1 = []
		path2 = []
		lca = self.FindLCA(root, first, second, path1, path2)
		if lca[1] is None:
			lca[1] = root
		p1_lca = -1
		for i in range(len(path1)):
			if path1[i][0] == lca[0]:
				p1_lca = i
				break
		p2_lca = -1
		for i in range(len(path2)):
			if path2[i][0] == lca[0]:
				p2_lca = i
				break
		cpath = []
		if len(path1[p1_lca:]) > 1:
			off = 1 if len(path2[p2_lca:]) > 1 else 0
			for i in range(len(path1) - 1, p1_lca - off, -1):
				cpath.append(path1[i])
		if len(path2[p2_lca:]) > 1:
			if len(cpath):
				cpath.extend(path2[p2_lca + 1:])
			else:
				for i in range(len(path2) - 1, p2_lca, -1):
					cpath.append(path2[i])
		turns = self.getTurns(cpath)
		return turns if turns != 0 else -1


class Solution:
	LEFT_TURN = 0
	RIGHT_TURN = 1

	@staticmethod
	def find_common_ancestor(root, first, second):
		if root is None:
			return root
		if root.data == first or root.data == second:
			return root
		node_found_in_left = Solution.find_common_ancestor(root.left, first, second)
		node_found_in_right = Solution.find_common_ancestor(root.right, first, second)
		if node_found_in_left and node_found_in_right:
			return root
		if node_found_in_left:
			return node_found_in_left
		if node_found_in_right:
			return node_found_in_right

	@staticmethod
	def find_path(root, tgt_val, running_path, path_list):
		if root is None:
			return
		if root.data == tgt_val:
			path_list.extend(running_path)
			return
		left_path_copy = running_path[:]
		left_path_copy.append(Solution.LEFT_TURN)
		Solution.find_path(root.left, tgt_val, left_path_copy, path_list)
		right_path_copy = running_path[:]
		right_path_copy.append(Solution.RIGHT_TURN)
		Solution.find_path(root.right, tgt_val, right_path_copy, path_list)

	def NumberOFTurns(self, root, first, second):
		if root is None:
			return 0
		if first == second:
			return 0
		ancestor = Solution.find_common_ancestor(root, first, second)
		path_to_first = []
		self.find_path(ancestor, first, [], path_to_first)
		path_to_second = []
		self.find_path(ancestor, second, [], path_to_second)
		path_to_first.reverse()
		path_to_first.extend(path_to_second)
		num_of_turns = 0
		path = path_to_first
		prev_path = path[0]
		for idx in range(1, len(path)):
			cur_path = path[idx]
			if prev_path != cur_path:
				num_of_turns += 1
			prev_path = cur_path
		return num_of_turns if num_of_turns != 0 else -1


class Solution:

	def NumberOFTurns(self, root, first, second):
		d1 = set()
		d2 = set()

		def dfs(root, target, d):
			if not root:
				return
			if root.data == target:
				d.add(root)
				return
			dfs(root.left, target, d)
			if root.left in d:
				d.add(root)
				return
			dfs(root.right, target, d)
			if root.right in d:
				d.add(root)
				return
		dfs(root, first, d1)
		dfs(root, second, d2)
		d = d1.intersection(d2)
		node = root
		while True:
			if node.left in d:
				node = node.left
			elif node.right in d:
				node = node.right
			else:
				break

		def turns(node, target, d):
			if node.data == target:
				return 0
			side = 0
			if node.right in d:
				side = 1
			cnt = 0
			while node.data != target:
				if node.left in d:
					if side == 1:
						cnt += 1
						side = 0
					node = node.left
				elif node.right in d:
					if side == 0:
						cnt += 1
						side = 1
					node = node.right
			return cnt
		if node.data == first:
			return turns(node, second, d2)
		if node.data == second:
			return turns(node, first, d1)
		return turns(node, first, d1) + turns(node, second, d2) + 1


class Solution:

	def __init__(self):
		self.node = -1
		self.count = 0

	def LCA(self, root, first, last):
		if root == None:
			return False
		left = self.LCA(root.left, first, last)
		right = self.LCA(root.right, first, last)
		if (left or right) and (root.data == first or root.data == last):
			self.node = root
		if left and right:
			self.node = root
		if left or right or root.data == first or (root.data == last):
			return True
		return False

	def turns(self, root, first, second, side, count=0):
		if root.data == first or root.data == second:
			self.count += count
		if root.left != None:
			if side == 'l':
				self.turns(root.left, first, second, 'l', count)
			else:
				self.turns(root.left, first, second, 'l', count + 1)
		if root.right != None:
			if side == 'r':
				self.turns(root.right, first, second, 'r', count)
			else:
				self.turns(root.right, first, second, 'r', count + 1)

	def NumberOFTurns(self, root, first, second):
		self.LCA(root, first, second)
		node = self.node
		if node == -1:
			return -1
		if node.left != None:
			self.turns(node.left, first, second, 'l')
		if node.right != None:
			self.turns(node.right, first, second, 'r')
		if (node.data == first or node.data == second) and self.count == 0:
			return -1
		if node.data == first or node.data == second:
			return self.count
		return self.count + 1


class Solution:

	def lca(self, root, first, second):
		if root == None:
			return False
		else:
			l = self.lca(root.left, first, second)
			r = self.lca(root.right, first, second)
			if root.data in [first, second]:
				c = True
			else:
				c = False
			if l and r or (l and c) or (r and c):
				self.lca_node = root
				return False
			return l or c or r

	def findPath(self, root, val, path):
		if root == None:
			return
		elif root.data == val:
			if path.strip():
				self.res.append(path)
			return
		else:
			self.findPath(root.left, val, path + 'l')
			self.findPath(root.right, val, path + 'r')
			return

	def findTurns(self, path):
		l = 0
		r = 1
		count = 0
		while r < len(path):
			if path[l] != path[r]:
				count += 1
			r += 1
			l += 1
		return count

	def NumberOFTurns(self, root, first, second):
		self.lca_node = None
		_ = self.lca(root, first, second)
		if self.lca_node == None:
			return 0
		self.res = []
		_ = self.findPath(self.lca_node, first, '')
		_ = self.findPath(self.lca_node, second, '')
		if len(self.res) == 1:
			return self.findTurns(self.res[0])
		else:
			return self.findTurns(self.res[0]) + 1 + self.findTurns(self.res[1])


class Solution:

	def lca(self, root, p, q):
		if not root:
			return None
		if root.data == q:
			return root
		if root.data == p:
			return root
		left = self.lca(root.left, p, q)
		right = self.lca(root.right, p, q)
		if not left and (not right):
			return None
		if left and (not right):
			return left
		if right and (not left):
			return right
		return root

	def turns(self, root, target, turn, c, arr, isfirst):
		if not root:
			return
		if root.data == target:
			arr[0] = c
			return
		if turn:
			x = c + 1
			if isfirst:
				x = c
			self.turns(root.left, target, turn, c, arr, False)
			self.turns(root.right, target, not turn, x, arr, False)
		else:
			self.turns(root.left, target, not turn, c + 1, arr, False)
			self.turns(root.right, target, turn, c, arr, False)

	def NumberOFTurns(self, root, first, second):
		lcaa = self.lca(root, first, second)
		c2 = [0]
		c3 = [0]
		self.turns(lcaa, first, True, 0, c2, True)
		self.turns(lcaa, second, True, 0, c3, True)
		if lcaa.data != first and lcaa.data != second:
			return c2[0] + c3[0] + 1
		return c2[0] + c3[0]


class Solution:

	def find_lca(self, root, first, second):
		if root is None:
			return None
		if root.data == first or root.data == second:
			return root
		left = self.find_lca(root.left, first, second)
		right = self.find_lca(root.right, first, second)
		if left and right:
			return root
		if left:
			return left
		return right

	def count_turns(self, root, key, turn, count):
		if root is None:
			return False
		if root.data == key:
			return True
		if turn:
			if self.count_turns(root.left, key, turn, count):
				return True
			if self.count_turns(root.right, key, not turn, count):
				count[0] += 1
				return True
		else:
			if self.count_turns(root.right, key, turn, count):
				return True
			if self.count_turns(root.left, key, not turn, count):
				count[0] += 1
				return True
		return False

	def NumberOFTurns(self, root, first, second):
		lca = self.find_lca(root, first, second)
		if lca is None:
			return -1
		count1 = [0]
		count2 = [0]
		self.count_turns(lca.left, first, True, count1) or self.count_turns(lca.right, first, False, count1)
		self.count_turns(lca.left, second, True, count2) or self.count_turns(lca.right, second, False, count2)
		if lca.data != first and lca.data != second:
			return count1[0] + count2[0] + 1
		if lca.data == first:
			return count2[0]
		if lca.data == second:
			return count1[0]
		return -1


class Solution:

	def __init__(self) -> None:
		self.path = []
		self.tmp = []

	def getPath(self, root, node):
		if not root:
			return
		if root.data == node:
			self.path = self.tmp.copy()
		self.tmp.append('L')
		self.getPath(root.left, node)
		self.tmp.pop()
		self.tmp.append('R')
		self.getPath(root.right, node)
		self.tmp.pop()

	def NumberOFTurns(self, root, first, second):
		self.getPath(root, first)
		path1 = self.path.copy()
		self.path.clear()
		self.tmp.clear()
		self.getPath(root, second)
		path2 = self.path.copy()
		n1 = len(path1)
		n2 = len(path2)
		no_of_turns = 0
		k = 0
		while k < n1 and k < n2 and (path1[k] == path2[k]):
			k += 1
		if k < n1 and k < n2 and (path1[k] != path2[k]):
			no_of_turns += 1
		tmp = k
		while tmp < n1 - 1:
			if path1[tmp] != path1[tmp + 1]:
				no_of_turns += 1
			tmp += 1
		tmp = k
		while tmp < n2 - 1:
			if path2[tmp] != path2[tmp + 1]:
				no_of_turns += 1
			tmp += 1
		return no_of_turns


class Solution:

	def NumberOFTurns(self, root, first, second):
		if first == second:
			return -1

		def lca(root):
			if not root:
				return None
			found = root.data in [first, second]
			left = lca(root.left)
			if found and left:
				return root
			right = lca(root.right)
			if found and right or (left and right) or found:
				return root
			return left or right

		def rec(target, root, direction):
			if not root:
				return -1
			if root.data == target:
				return 0
			l_count = rec(target, root.left, 'L')
			if l_count != -1:
				return l_count + (1 if direction == 'R' else 0)
			r_count = rec(target, root.right, 'R')
			if r_count != -1:
				return r_count + (1 if direction == 'L' else 0)
			return -1
		ancs = lca(root)
		if ancs.data == first:
			return rec(second, ancs, None)
		if ancs.data == second:
			return rec(first, ancs, None)
		return rec(first, ancs, None) + rec(second, ancs, None) + 1


class Solution:

	def NumberOFTurns(self, root, first, second):
		if first == second:
			return -1

		def rec(root, direction, count):
			if not root:
				return -1
			found = root.data in [first, second]
			l_count = r_count = -1
			if direction == 'L':
				l_count = rec(root.left, 'L', 0 if found else count)
				r_count = rec(root.right, 'R', 0 if found else count + 1)
			else:
				l_count = rec(root.left, 'L', 0 if found else count + 1)
				r_count = rec(root.right, 'R', 0 if found else count)
			if found and l_count != -1:
				return l_count
			if found and r_count != -1:
				return r_count
			if l_count != -1 and r_count != -1:
				return l_count - count + (r_count - count)
			if found:
				return count
			return max(l_count, r_count)
		return rec(root, 'L', 0) or -1


class Solution:

	def finddipth(self, root, direction, k):
		if root is None:
			return -1
		if root.data == k:
			return 0
		val = self.finddipth(root.left, 'left', k)
		if root.left and val != -1:
			return val + int(direction == 'right')
		val = self.finddipth(root.right, 'right', k)
		if root.right and val != -1:
			return val + int(direction == 'left')
		return -1

	def findLCA(self, root, first, second):
		if root is None:
			return None
		if root.data == first or root.data == second:
			return root
		leftLCA = self.findLCA(root.left, first, second)
		rightLCA = self.findLCA(root.right, first, second)
		if leftLCA and rightLCA:
			return root
		if leftLCA:
			return leftLCA
		return rightLCA

	def NumberOFTurns(self, root, first, second):
		LCA = self.findLCA(root, first, second)
		res = 0
		if LCA.data == first:
			res = self.finddipth(LCA, 'direction', second)
		elif LCA.data == second:
			res = self.finddipth(LCA, 'direction', first)
		else:
			res = self.finddipth(LCA, 'direction', first) + self.finddipth(LCA, 'direction', second) + 1
		return res


class Solution:

	def NumberOFTurns(self, root, first, second):

		def lca(root, nd1, nd2):
			if not root:
				return
			if root.data == nd1 or root.data == nd2:
				return root
			l = lca(root.left, nd1, nd2)
			r = lca(root.right, nd1, nd2)
			if l and r:
				return root
			return l or r
		x = lca(root, first, second)

		def func(root, v, prev):
			if not root:
				return float('inf')
			if root.data == v:
				return 0
			if prev == -1:
				return min(func(root.left, v, -1), 1 + func(root.right, v, 1))
			elif prev == 1:
				return min(1 + func(root.left, v, -1), func(root.right, v, 1))
			else:
				return min(1 + func(root.left, v, -1), 1 + func(root.right, v, 1))
		return func(x, first, 0) + func(x, second, 0) - 1


class Solution:

	def NumberOFTurns(self, root, first, second):

		def lca(root, f, s):
			if not root:
				return
			if root.data == f or root.data == s:
				return root
			left = lca(root.left, f, s)
			right = lca(root.right, f, s)
			if left and right:
				return root
			return left or right
		rt = lca(root, first, second)

		def func(root, v, prev):
			if not root:
				return float('inf')
			if root.data == v:
				return 0
			if prev == -1:
				return min(func(root.left, v, -1), 1 + func(root.right, v, 1))
			elif prev == 1:
				return min(1 + func(root.left, v, -1), func(root.right, v, 1))
			else:
				return min(1 + func(root.left, v, -1), 1 + func(root.right, v, 1))
		return func(rt, first, 0) + func(rt, second, 0) - 1


class Solution:

	def is_in_subtree(self, root, node):
		if root is None:
			return False
		elif root == node:
			return True
		else:
			return self.is_in_subtree(root.left, node) or self.is_in_subtree(root.right, node)

	def get_path(self, root, data):
		if root is None:
			return None
		if root.data == data:
			return []
		left_path = self.get_path(root.left, data)
		right_path = self.get_path(root.right, data)
		if left_path is not None:
			return ['left'] + left_path
		elif right_path is not None:
			return ['right'] + right_path

	def get_num_turns(self, l):
		turns = 0
		for i in range(len(l) - 1):
			if l[i] != l[i + 1]:
				turns += 1
		return turns

	def NumberOFTurns(self, root, first, second):
		first_path = self.get_path(root, first)
		second_path = self.get_path(root, second)
		i = 0
		l1 = len(first_path)
		l2 = len(second_path)
		while i < l1 and i < l2 and (first_path[i] == second_path[i]):
			i += 1
		turns = 0
		if i < l1:
			turns += self.get_num_turns(first_path[i:])
		if i < l2:
			turns += self.get_num_turns(second_path[i:])
		if i < l1 and i < l2:
			turns += 1
		if turns == 0:
			turns = -1
		return turns


class Solution:

	def NumberOFTurnsRec(self, root, first, second, mode):
		if root == None:
			return (None, None, None)
		(l1, l2, l_turns) = self.NumberOFTurnsRec(root.left, first, second, 'left')
		(r1, r2, r_turns) = self.NumberOFTurnsRec(root.right, first, second, 'right')
		if l_turns is not None:
			return (l1, l2, l_turns)
		if r_turns is not None:
			return (r1, r2, r_turns)
		turns1 = None
		turns2 = None
		turns = None
		if l1 is not None and r2 is not None:
			turns = l1 + r2 + 1
		elif l2 is not None and r1 is not None:
			turns = l2 + r1 + 1
		elif l1 is not None:
			turns1 = l1
			if mode != 'left':
				turns1 += 1
			if root.data == second:
				turns = l1
		elif l2 is not None:
			turns2 = l2
			if mode != 'left':
				turns2 += 1
			if root.data == first:
				turns = l2
		elif r1 is not None:
			turns1 = r1
			if mode != 'right':
				turns1 += 1
			if root.data == second:
				turns = r1
		elif r2 is not None:
			turns2 = r2
			if mode != 'right':
				turns2 += 1
			if root.data == first:
				turns = r2
		elif root.data == first:
			turns1 = 0
		elif root.data == second:
			turns2 = 0
		return (turns1, turns2, turns)

	def NumberOFTurns(self, root, first, second):
		(_, _, turns) = self.NumberOFTurnsRec(root, first, second, 'root')
		if turns is None:
			return -1
		else:
			return turns


class Solution:

	def NumberOFTurns(self, root, first, second):

		def lca(r):
			if not r:
				return None
			if r.data == first or r.data == second:
				return r
			left = lca(r.left)
			right = lca(r.right)
			if left and right:
				return r
			return left if left else right
		count = [0]

		def countTurns(r, isLeft, c, target):
			if not r:
				return False
			if r.data == target:
				count[0] = c
				return True
			if isLeft:
				left = countTurns(r.left, True, c, target)
				right = countTurns(r.right, False, c + 1, target)
			else:
				left = countTurns(r.left, True, c + 1, target)
				right = countTurns(r.right, False, c, target)
			return left or right
		lcaNode = lca(root)
		if lcaNode.data != first and lcaNode.data != second:
			temp = 0
			left1 = countTurns(lcaNode.left, True, 0, first)
			if left1:
				temp += count[0]
			else:
				right1 = countTurns(lcaNode.right, False, 0, first)
				temp += count[0]
			count[0] = 0
			left2 = countTurns(lcaNode.left, True, 0, second)
			if left2:
				temp += count[0]
			else:
				right2 = countTurns(lcaNode.right, False, 0, second)
				temp += count[0]
			return temp + 1
		if lcaNode.data == first:
			target = second
		else:
			target = first
		left = countTurns(lcaNode.left, True, 0, target)
		if left:
			return count[0]
		else:
			right = countTurns(lcaNode.right, False, 0, target)
			return count[0]


def lca(root, f, s):
	if root is None:
		return None
	if root.data == f or root.data == s:
		return root
	left = lca(root.left, f, s)
	right = lca(root.right, f, s)
	if left and right:
		return root
	if left:
		return left
	else:
		return right

def count(root, first, second, d, ans, turns):
	if root is None:
		return
	if root.data == first or root.data == second:
		ans[0] = turns
		return
	if d == 0:
		count(root.left, first, second, 0, ans, turns)
		count(root.right, first, second, 1, ans, turns + 1)
	else:
		count(root.left, first, second, 0, ans, turns + 1)
		count(root.right, first, second, 1, ans, turns)

class Solution:

	def NumberOFTurns(self, root, first, second):
		node = lca(root, first, second)
		x = [0]
		y = [0]
		count(node.left, first, second, 0, x, 0)
		count(node.right, first, second, 1, y, 0)
		if node.data == first or node.data == second:
			return x[0] + y[0]
		else:
			return x[0] + y[0] + 1


class Solution:

	def NumberOFTurns(self, root, first, second):
		ans = [None]

		def findAncestor(root, first, second):
			if root is None:
				return None
			if root.data in [first, second]:
				ans[0] = root
				return True
			l = findAncestor(root.left, first, second)
			r = findAncestor(root.right, first, second)
			if l and r:
				ans[0] = root
				return
			if l or r:
				return True
		num1 = [0]

		def numTurns(cur, node, left, right, num):
			if cur == None:
				return
			if cur.data == node:
				num1[0] = num
				return
			else:
				n1 = 1 if right else 0
				numTurns(cur.left, node, True, False, num + n1)
				n2 = 1 if left else 0
				numTurns(cur.right, node, False, True, num + n2)
		findAncestor(root, first, second)
		ancestor = ans[0]
		if ancestor.data == first:
			numTurns(ancestor, second, False, False, 0)
			return num1[0]
		elif ancestor.data == second:
			numTurns(ancestor, first, False, False, 0)
			return num1[0]
		else:
			numTurns(ancestor, first, False, False, 0)
			temp = num1[0]
			num1[0] = 0
			numTurns(ancestor, second, False, False, 0)
			temp += num1[0]
			return temp + 1


class Solution:
	ans = []

	def lca(self, root, n1, n2):
		if root == None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		left = self.lca(root.left, n1, n2)
		right = self.lca(root.right, n1, n2)
		if left and right:
			return root
		return left if left else right

	def path(self, a, root, val):
		if root == None:
			return False
		if root.data == val:
			self.ans.append(a)
			return True
		x1 = self.path(a + 'L', root.left, val)
		x2 = self.path(a + 'R', root.right, val)
		if x1 or x2:
			return True
		return False

	def NumberOFTurns(self, root, first, second):
		self.ans = []
		node = self.lca(root, first, second)
		a = ''
		self.path(a, node, first)
		a = ''
		self.path(a, node, second)
		ans = self.ans[0][::-1] + self.ans[1]
		res = 0
		for i in range(1, len(ans)):
			res += ans[i] != ans[i - 1]
		return res


class Solution:

	def NumberOFTurns(self, root, first, second):

		def LCA(node, node1, node2):
			if not node:
				return None
			if node.data == node1 or node.data == node2:
				return node
			a = LCA(node.left, node1, node2)
			b = LCA(node.right, node1, node2)
			if a and b:
				return node
			return a if a else b
		lca = LCA(root, first, second)

		def path(root, node, s):
			if not root:
				return ''
			if root.data == node:
				return s
			return path(root.left, node, s + 'L') or path(root.right, node, s + 'R')
		l = path(lca, first, '')
		r = path(lca, second, '')
		l = l[::-1]
		total = l + r
		ans = 0
		for i in range(1, len(total)):
			if total[i] != total[i - 1]:
				ans += 1
		return ans


class Solution:

	def find(self, root, nodes):
		if root == None:
			return None
		if root.data == nodes[0] or root.data == nodes[1]:
			return root
		l = self.find(root.left, nodes)
		r = self.find(root.right, nodes)
		if l == None:
			return r
		elif r == None:
			return l
		else:
			return root

	def findPath(self, root, val, path):
		if root == None:
			return
		elif root.data == val:
			self.res.update({val: path})
			return
		else:
			self.findPath(root.left, val, path + 'l')
			self.findPath(root.right, val, path + 'r')
			return

	def findTurns(self, path):
		l = 0
		r = 1
		count = 0
		while r < len(path):
			if path[l] != path[r]:
				count += 1
			r += 1
			l += 1
		return count

	def NumberOFTurns(self, root, first, second):
		lca = self.find(root, [first, second])
		if lca == None:
			return -1
		self.res = dict()
		self.findPath(lca, first, '')
		self.findPath(lca, second, '')
		count = 0
		if lca.data == first:
			if self.res.get(second) is None:
				return -1
			else:
				return self.findTurns(self.res[second])
		elif lca.data == second:
			if self.res.get(first) is None:
				return -1
			else:
				return self.findTurns(self.res[first])
		else:
			return 1 + self.findTurns(self.res[first]) + self.findTurns(self.res[second])


class Solution:

	def find(self, node, value, turns):
		if node.data == value:
			return turns
		if node.left:
			ret = self.find(node.left, value, turns + 'L')
			if ret:
				return ret
		if node.right:
			ret = self.find(node.right, value, turns + 'R')
			if ret:
				return ret
		return

	def count(self, s):
		c = 0
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				continue
			else:
				c += 1
		return c

	def NumberOFTurns(self, root, first, second):
		turns1 = self.find(root, first, '')
		turns2 = self.find(root, second, '')
		n1 = len(turns1)
		n2 = len(turns2)
		start1 = 0
		start2 = 0
		while start1 < n1 and start2 < n2:
			if turns1[start1] == turns2[start2]:
				start1 += 1
				start2 += 1
			else:
				break
		if start1 == n1:
			return self.count(turns2[start2:])
		elif start2 == n2:
			return self.count(turns1[start1:])
		else:
			if turns1[start1] == 'L':
				x = turns1[start1:]
				x = x[::-1]
				y = turns2[start2:]
			else:
				x = turns2[start2:]
				x = x[::-1]
				y = turns1[start1:]
			s = x + y
			return self.count(s)


class Solution:

	def NumberOFTurns(self, root, first, second):

		def lca(root, p, q):
			if root:
				if root.data == p or root.data == q:
					return root
				left = lca(root.left, p, q)
				right = lca(root.right, p, q)
				if left is None and right is None:
					return None
				if left is None and right is not None:
					return right
				if left is not None and right is None:
					return left
				return root
			return None
		one = [-1, -1]

		def find_turn(root, p, last, turn):
			if root:
				if root.data == p:
					if one[0] != -1:
						one[1] = turn
					else:
						one[0] = turn
					return
				if last == '':
					find_turn(root.left, p, 'left', turn)
					find_turn(root.right, p, 'right', turn)
				elif last == 'left':
					find_turn(root.left, p, 'left', turn)
					find_turn(root.right, p, 'right', turn + 1)
				else:
					find_turn(root.left, p, 'left', turn + 1)
					find_turn(root.right, p, 'right', turn)
		ancestor = lca(root, first, second)
		(p, q) = (first, second)
		find_turn(ancestor, p, '', 0)
		find_turn(ancestor, q, '', 0)
		if ancestor.data == p or ancestor.data == q:
			return max(one)
		return sum(one) + 1
		return 9


from collections import deque
path = deque()

def roottonode(root, x, path):
	if root is None:
		return (False, path)
	if root.data == x:
		return (True, path)
	rt_chk = False
	if root.left:
		path.append('left')
		(rt_chk, path) = roottonode(root.left, x, path)
		if rt_chk == False:
			path.pop()
	if rt_chk == False:
		if root.right:
			path.append('right')
			(rt_chk, path) = roottonode(root.right, x, path)
			if rt_chk == False:
				path.pop()
	return (rt_chk, path)

def turnsab(path1, path2):
	while len(path1) > 0 and len(path2) > 0:
		if path1[0] == path2[0]:
			path1.popleft()
			path2.popleft()
		else:
			break
	path1.reverse()
	path1.extend(list(path2))
	rslt = 0
	if len(path1) <= 1:
		rslt = -1
	else:
		prv = path1.popleft()
		while len(path1) > 0:
			cr = path1.popleft()
			if prv != cr:
				rslt = rslt + 1
			prv = cr
	if rslt == 0:
		rslt = -1
	return rslt

class Solution:

	def NumberOFTurns(self, root, first, second):
		pat1 = deque()
		(rt_chk1, path1) = roottonode(root, first, pat1)
		pat2 = deque()
		(rt_chk2, path2) = roottonode(root, second, pat2)
		rslt = turnsab(path1, path2)
		return rslt


class Solution:

	def NumberOFTurns(self, root, first, second):
		comm = self.lca(root, first, second)
		x = 0
		y = 0

		def count(root, first, second, dire, turns):
			if not root:
				return (None, turns)
			if root.data == first or root.data == second:
				return (True, turns)
			(left, turns) = count(root.left, first, second, 0, turns)
			if left:
				if dire == 1:
					turns += 1
				return (True, turns)
			(right, turns) = count(root.right, first, second, 1, turns)
			if right:
				if dire == 0:
					turns += 1
				return (True, turns)
			return (False, turns)
		x = 0
		y = 0
		x = count(comm.left, first, second, 0, x)[1]
		y = count(comm.right, first, second, 1, y)[1]
		if comm.data == first or comm.data == second:
			return x + y
		else:
			return x + y + 1

	def lca(self, root, first, second):
		if not root:
			return root
		if root.data == first or root.data == second:
			return root
		left = self.lca(root.left, first, second)
		right = self.lca(root.right, first, second)
		if left and right:
			return root
		if left:
			return left
		return right


class Solution:

	def NumberOFTurns(self, root, first, second):

		def lca(curr, p, q):
			if curr is None or curr.data == p or curr.data == q:
				return curr
			left = lca(curr.left, p, q)
			right = lca(curr.right, p, q)
			if left is not None and right is not None:
				return curr
			return left if left else right
		ances = lca(root, first, second)

		def finder(curr, x, val, isleft):
			if not curr:
				return (False, val)
			if curr.data == x:
				return (True, val)
			(left, val1) = finder(curr.left, x, val, 1)
			(right, val2) = finder(curr.right, x, val, 0)
			val = max(val1, val2)
			if curr.data == ances.data:
				return (True, val)
			if isleft:
				if left:
					return (True, val)
				elif right:
					return (True, val + 1)
				else:
					return (False, val)
			elif left:
				return (True, val + 1)
			elif right:
				return (True, val)
			else:
				return (False, val)
		res1 = finder(ances, first, 0, 0)
		res2 = finder(ances, second, 0, 0)
		ans = res1[1] + res2[1]
		if ances.data == first or ances.data == second:
			return ans
		else:
			return ans + 1


class Solution:

	def NumberOFTurns(self, root, a, b):
		global c
		c = 0
		lca = self.lca(root, a, b)
		if lca is None:
			return -1
		if lca.data != a and lca.data != b:
			if self.count(lca.left, b, True) or self.count(lca.right, b, False):
				pass
			if self.count(lca.left, a, True) or self.count(lca.right, a, False):
				pass
			return c + 1
		if lca.data == a:
			self.count(lca.right, b, False)
			self.count(lca.left, b, True)
			return c
		if lca.data == b:
			self.count(lca.right, a, False)
			self.count(lca.left, a, True)
			return c

	def count(self, root, k, t):
		global c
		if root is None:
			return False
		if root.data == k:
			return True
		if t:
			if self.count(root.left, k, t):
				return True
			if self.count(root.right, k, not t):
				c += 1
				return True
		else:
			if self.count(root.right, k, t):
				return True
			if self.count(root.left, k, not t):
				c += 1
				return True
		return False

	def lca(self, root, a, b):
		if root is None:
			return 0
		if root.data == a or root.data == b:
			return root
		l = self.lca(root.left, a, b)
		r = self.lca(root.right, a, b)
		if l and r:
			return root
		if not r:
			return l
		return r


class Solution:

	def lca(self, root, n1, n2):
		if root == None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		l = self.lca(root.left, n1, n2)
		r = self.lca(root.right, n1, n2)
		if l != None and r != None:
			return root
		if l:
			return l
		return r

	def find(self, root, x, s):
		if root == None:
			return False
		if root.data == x:
			return True
		s.append('L')
		if self.find(root.left, x, s):
			return True
		s.pop()
		s.append('R')
		if self.find(root.right, x, s):
			return True
		s.pop()
		return False

	def NumberOFTurns(self, root, first, second):
		p = self.lca(root, first, second)
		s = []
		r = []
		self.find(p, first, s)
		self.find(p, second, r)
		ans = 0
		for i in range(len(s) - 1):
			if s[i] != s[i + 1]:
				ans += 1
		for i in range(len(r) - 1):
			if r[i] != r[i + 1]:
				ans += 1
		if s and r and (s[0] != r[0]):
			return ans + 1
		return ans