Given a binary tree and two node values your task is to find the minimum distance between them.
The given two nodes are guaranteed to be in the binary tree and nodes are numbered from 1 to N.
Please Note that a and b are not always leaf node.
Example 1:
Input:
        1
      /  \
     2    3
a = 2, b = 3
Output: 2
Explanation: The tree formed is:
       1
     /   \ 
    2     3
We need the distance between 2 and 3.
Being at node 2, we need to take two
steps ahead in order to reach node 3.
The path followed will be:
2 -> 1 -> 3. Hence, the result is 2. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findDist() which takes the root node of the Tree and the two node values a and b as input parameters and returns the minimum distance between the nodes represented by the two given node values.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 10^{4}
1 <= Data of a node <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

class Solution:

    def findDist(self,root,a,b):

    

        #return: minimum distance between a and b in a tree with given root

        #code here

Solutions:
class Solution:

	def findDist(self, root, a, b):

		def LCA(root, path, tar):
			if root == None:
				return
			if root.data == tar:
				self.ans.append(path + [root.data])
			LCA(root.left, path + [root.data], tar)
			LCA(root.right, path + [root.data], tar)
		self.ans = []
		LCA(root, [], a)
		ans1 = self.ans[0]
		self.ans = []
		LCA(root, [], b)
		ans2 = self.ans[0]
		for i in range(min(len(ans1), len(ans2))):
			if ans1[i] == ans2[i]:
				val = i + 1
			else:
				return len(ans1) + len(ans2) - 2 * val
		return len(ans1) + len(ans2) - 2 * val


class Solution:

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

	def dist(self, root, v):
		if root == None:
			return None
		if root.data == v:
			return 0
		l = self.dist(root.left, v)
		r = self.dist(root.right, v)
		if l != None:
			return l + 1
		elif r != None:
			return r + 1
		else:
			return None

	def findDist(self, root, a, b):
		p = self.util(root, a, b)
		if p == None:
			return 0
		elif p.data == a:
			return self.dist(p, b)
		elif p.data == b:
			return self.dist(p, a)
		else:
			return self.dist(p, a) + self.dist(p, b)


class Solution:

	def lca(self, root, a, b):
		if not root or root.data == a or root.data == b:
			return root
		left = self.lca(root.left, a, b)
		right = self.lca(root.right, a, b)
		if not left:
			return right
		elif not right:
			return left
		else:
			return root

	def calc(self, r, a):
		if not r:
			return 100000000.0
		if r.data == a:
			return 0
		left = 1 + self.calc(r.left, a)
		right = 1 + self.calc(r.right, a)
		return min(left, right)

	def findDist(self, root, a, b):
		x = self.lca(root, a, b)
		return self.calc(x, a) + self.calc(x, b)


class Solution:

	def findDist(self, root, a, b):

		def findNodeDist(root, a, b, ans):
			if not root:
				return 0
			left = findNodeDist(root.left, a, b, ans)
			right = findNodeDist(root.right, a, b, ans)
			if root.data == a or root.data == b:
				if left or right:
					ans[0] = max(left, right)
					return 0
				else:
					return 1
			if left and right:
				ans[0] = left + right
				return 0
			if left or right:
				return max(left, right) + 1
			return 0
		ans = [0]
		findNodeDist(root, a, b, ans)
		return ans[0]


class Solution:

	def findDist(self, root, a, b):

		def search(root, x):
			if root is None:
				return [-1]
			elif root.data == x:
				return [root]
			l = r = [-1]
			if root.left is not None:
				l = search(root.left, x)
			if l[0] == -1 and root.right is not None:
				r = search(root.right, x)
			if l[0] != -1:
				l.insert(0, root)
				return l
			elif r[0] != -1:
				r.insert(0, root)
				return r
			else:
				return [-1]
		first = search(root, a)
		second = search(root, b)
		i = j = 0
		while i < len(first) and j < len(second) and (first[i] == second[j]):
			i += 1
			j += 1
		dist = len(first) - i + len(second) - j
		return dist


class Solution:

	def findDist(self, root, a, b):
		out = []

		def traverse(root, k, path=[]):
			if not root:
				return
			if root.data == k:
				path.append(str(root.data))
				temp = '.'.join(path)
				out.append(temp)
				return
			path.append(str(root.data))
			traverse(root.left, k, path)
			traverse(root.right, k, path)
			path.pop()
		traverse(root, a, [])
		traverse(root, b, [])
		out[0] = out[0].split('.')
		out[1] = out[1].split('.')
		a = set(out[0])
		b = set(out[1])
		count = 0
		if a.intersection(b) == len(a) or a.intersection(b) == len(b):
			return len(a) - len(b)
		else:
			return len(a.union(b) - a.intersection(b))


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
		elif l != None and r == None:
			return l
		elif l == None and r != None:
			return r
		return None

	def height(self, root, v):
		if root == None:
			return None
		if root.data == v:
			return 0
		l = self.height(root.left, v)
		r = self.height(root.right, v)
		if l != None:
			return 1 + l
		elif r != None:
			return 1 + r

	def findDist(self, root, a, b):
		n = self.lca(root, a, b)
		if n == None:
			return 0
		elif n.data == a:
			return self.height(n, b)
		elif n.data == b:
			return self.height(n, a)
		else:
			a = self.height(n, a)
			b = self.height(n, b)
			return a + b


class Solution:

	def findDist(self, root, a, b):

		def findnode(root, a, b):
			if root is None:
				return None
			if root.data == a or root.data == b:
				return root
			ans1 = findnode(root.left, a, b)
			ans2 = findnode(root.right, a, b)
			if ans1 and ans2:
				return root
			if ans1:
				return ans1
			if ans2:
				return ans2

		def find(root, key):
			if root is None:
				return 0
			if root.data == key:
				return 1
			ans1 = find(root.left, key)
			ans2 = find(root.right, key)
			if ans1:
				return 1 + ans1
			if ans2:
				return 1 + ans2
			return 0
		root1 = findnode(root, a, b)
		node1 = find(root1, a)
		node2 = find(root1, b)
		return node1 + node2 - 2


class Solution:

	def findDist(self, root, a, b):
		res = self.findDistHelper(root, a, b)
		return res if res >= 0 else 0

	def findDistHelper(self, root, a, b):
		if root == None:
			return 0
		l = self.findDistHelper(root.left, a, b)
		if l > 0:
			return l
		r = self.findDistHelper(root.right, a, b)
		if r > 0:
			return r
		if root.data == a or root.data == b:
			if l < 0 or r < 0:
				return abs(l + r)
			return -1
		elif l < 0 and r < 0:
			return abs(l + r)
		elif l < 0 and r == 0:
			return -1 + l
		elif r < 0 and l == 0:
			return -1 + r
		return 0


class Solution:

	def findDist(self, root, a, b):
		res = [0]
		self.helper(root, a, b, res)
		return res[0]

	def helper(self, root, a, b, res):
		if root == None:
			return 0
		(l, r) = (self.helper(root.left, a, b, res), self.helper(root.right, a, b, res))
		if root.data == a or root.data == b:
			if l != 0 or r != 0:
				res[0] = max(l, r) if res[0] == 0 else min(res[0], max(l, r))
				return 0
			return 1
		if l != 0 and r != 0:
			res[0] = l + r if res[0] == 0 else min(res[0], l + r)
			return 0
		elif l != 0 or r != 0:
			return 1 + max(l, r)
		return 0


class Solution:

	def findDist(self, root, a, b):
		(ra, rb) = ([], [])

		def solveA(root, arr, a):
			if not root:
				return False
			if root:
				if root.data == a:
					arr.append(root.data)
					return True
				ls = solveA(root.left, arr, a)
				if ls:
					arr.append(root.data)
				rs = solveA(root.right, arr, a)
				if rs:
					arr.append(root.data)
				return rs or ls
		solveA(root, ra, a)
		solveA(root, rb, b)
		while ra[-1] == rb[-1]:
			ra.pop()
			rb.pop()
			if not ra or not rb:
				break
		ans = len(ra) + len(rb)
		return ans


class Solution:

	def findDist(self, root, a, b):
		common_point = self.lca(root, a, b)
		x = self.findeachsidedis(common_point, a)
		y = self.findeachsidedis(common_point, b)
		return x + y - 2

	def findeachsidedis(self, root, value):
		if root is None:
			return 0
		if root.data == value:
			return 1
		left = self.findeachsidedis(root.left, value)
		right = self.findeachsidedis(root.right, value)
		if left == 0 and right == 0:
			return 0
		else:
			return left + right + 1

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


class Solution:

	def findDist(self, root, a, b):

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

		def pathLength(root, data):
			if root == None:
				return None
			if root.data == data:
				return 0
			left = pathLength(root.left, data)
			if left != None:
				return left + 1
			right = pathLength(root.right, data)
			if right != None:
				return right + 1
			return None
		commonParent = lca(root, a, b)
		return pathLength(root, a) + pathLength(root, b) - 2 * pathLength(root, commonParent.data)

	def findDist(self, root, a, b):

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

		def pathLength(root, data):
			if root == None:
				return None
			if root.data == data:
				return 0
			left = pathLength(root.left, data)
			if left != None:
				return left + 1
			right = pathLength(root.right, data)
			if right != None:
				return right + 1
			return None
		commonParent = lca(root, a, b)
		return pathLength(commonParent, a) + pathLength(commonParent, b)


class Solution:

	def findDist(self, root, a, b):

		def findDist(root, dest):
			if root == None:
				return 0
			elif root.data == dest:
				return 1
			l = findDist(root.left, dest)
			r = findDist(root.right, dest)
			if l > 0 or r > 0:
				return max(l, r) + 1
			else:
				return 0

		def lca(root, a, b):
			if root == None:
				return root
			if root.data == a or root.data == b:
				return root
			l = lca(root.left, a, b)
			r = lca(root.right, a, b)
			if l == None:
				return r
			elif r == None:
				return l
			else:
				return root
		LCA = lca(root, a, b)
		dist1 = findDist(LCA, a) - 1
		dist2 = findDist(LCA, b) - 1
		return dist1 + dist2


class Solution:

	def solution(self, root, a, b):
		if root == None:
			return
		if root.data == a or root.data == b:
			return root
		left = self.solution(root.left, a, b)
		right = self.solution(root.right, a, b)
		if left and right:
			return root
		return left if left is not None else right

	def findLength(self, root, a):
		if root == None:
			return 1000000000.0
		if root.data == a:
			return 0
		l = 1 + self.findLength(root.left, a)
		r = 1 + self.findLength(root.right, a)
		return min(l, r)

	def findDist(self, root, a, b):
		if root == None:
			return
		node = self.solution(root, a, b)
		return self.findLength(node, a) + self.findLength(node, b)


class Solution:

	def findDist(self, root, a, b):

		def findlca(root):
			if root == None:
				return
			if root.data == a or root.data == b:
				return root
			left = findlca(root.left)
			right = findlca(root.right)
			if root.data in (a, b):
				return root
			if not left and (not right):
				return None
			if left and (not right):
				return left
			if not left and right:
				return right
			return root

		def finddis(root, x):
			if not root:
				return 0
			if root.data == x:
				return 1
			left = finddis(root.left, x)
			right = finddis(root.right, x)
			d = left + right + 1
			if left == 0 and right == 0:
				return 0
			return d
		lca = findlca(root)
		d1 = finddis(lca, a)
		d2 = finddis(lca, b)
		return d1 + d2 - 2


class Solution:

	def findDist(self, root, a, b):

		def findlca(root, a, b):
			if root == None:
				return
			if root.data == a or root.data == b:
				return root
			l = findlca(root.left, a, b)
			r = findlca(root.right, a, b)
			if l and r:
				return root
			if l:
				return l
			return r

		def dist(root, x):
			if root == None:
				return 0
			if root.data == x:
				return 1
			a = dist(root.left, x)
			b = dist(root.right, x)
			if a == 0 and b == 0:
				return 0
			return a + b + 1
		lca = findlca(root, a, b)
		p = dist(lca, a)
		q = dist(lca, b)
		return p + q - 2


class Solution:

	def lca(self, root, a, b):
		if root == None:
			return
		if root.data == a or root.data == b:
			return root
		left = self.lca(root.left, a, b)
		right = self.lca(root.right, a, b)
		if left and right:
			return root
		if left != None:
			return left
		else:
			return right

	def dis(self, root, a):
		if root == None:
			return 100000
		if root.data == a:
			return 0
		l = 1 + self.dis(root.left, a)
		m = 1 + self.dis(root.right, a)
		return min(l, m)

	def findDist(self, root, a, b):
		k = self.lca(root, a, b)
		return self.dis(k, a) + self.dis(k, b)


class Solution:
	dist = 0

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

	def find_dis(self, root, n, level):
		if not root:
			return 0
		if root.data == n:
			self.dist = self.dist + level
			return level
		self.find_dis(root.left, n, level + 1)
		self.find_dis(root.right, n, level + 1)

	def findDist(self, root, a, b):
		lca_root = self.lca(root, a, b)
		self.find_dis(lca_root, a, 0)
		self.find_dis(lca_root, b, 0)
		return self.dist


class Solution:

	def findDist(self, root, a, b):
		self.dist = 0
		lca_root = self.lca(root, a, b)
		self.dis(lca_root, a, 0)
		self.dis(lca_root, b, 0)
		return self.dist

	def lca(self, rt, a, b):
		if rt is None:
			return None
		if rt.data == a or rt.data == b:
			return rt
		ln = self.lca(rt.left, a, b)
		rn = self.lca(rt.right, a, b)
		if ln and rn:
			return rt
		if ln:
			return ln
		if rn:
			return rn
		return None

	def dis(self, rt, n, level):
		if not rt:
			return 0
		if rt.data == n:
			self.dist = self.dist + level
			return level
		self.dis(rt.left, n, level + 1)
		self.dis(rt.right, n, level + 1)


class Solution:

	def findDist(self, root, a, b):

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

		def dis(root, n):
			if root == None:
				return -1
			elif root.data == n:
				return 0
			else:
				l = dis(root.left, n)
				r = dis(root.right, n)
				d = max(l, r)
				return 1 + d if d >= 0 else -1
		lc = lca(root, a, b)
		return dis(lc, a) + dis(lc, b)


class Solution:

	def findDist(self, root, a, b):
		res1 = []
		res2 = []

		def find(root, j, l, val):
			cou = 0
			for i in range(j, len(l)):
				if root.data == val:
					return cou
				elif l[i] == 'r':
					root = root.right
				else:
					root = root.left
				cou += 1
			return cou
		q = deque()
		q.append((root, []))
		while q:
			(n, l1) = q.popleft()
			if n.data == a:
				res1 = l1
			if n.data == b:
				res2 = l1
			if n.left:
				q.append((n.left, l1 + ['l']))
			if n.right:
				q.append((n.right, l1 + ['r']))
			if len(res1) > 1 and len(res2) > 1:
				break
		m = min(len(res1), len(res2))
		j = 0
		for i in range(m):
			if res1[i] != res2[i]:
				break
			elif res1[i] == 'r':
				root = root.right
			else:
				root = root.left
			j = i + 1
		count = 0
		count += find(root, j, res2, b)
		count += find(root, j, res1, a)
		return count


class Node:

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

class Solution:

	def lca(self, root, a, b):
		if root is None:
			return
		if root.data == a or root.data == b:
			return root
		leftAns = self.lca(root.left, a, b)
		rightAns = self.lca(root.right, a, b)
		if leftAns != None and rightAns == None:
			return leftAns
		if rightAns != None and leftAns == None:
			return rightAns
		if leftAns != None and rightAns != None:
			return root
		return None

	def height(self, root, x):
		if root is None:
			return -1
		if root.data == x:
			return 0
		leftHeight = self.height(root.left, x)
		rightHeight = self.height(root.right, x)
		if leftHeight == -1 and rightHeight == -1:
			return -1
		elif leftHeight == -1:
			return rightHeight + 1
		else:
			return leftHeight + 1

	def findDist(self, root, a, b):
		ancestor = self.lca(root, a, b)
		h1 = self.height(ancestor, a)
		h2 = self.height(ancestor, b)
		return h1 + h2


class Solution:

	def findDist(self, root, a, b):
		if root == None:
			return 0

		def pathtoNode(root, path, k):
			if root == None:
				return False
			path.append(root.data)
			if root.data == k:
				return True
			if root.left != None and pathtoNode(root.left, path, k) or (root.right != None and pathtoNode(root.right, path, k)):
				return True
			path.pop()
			return False
		p1 = []
		pathtoNode(root, p1, a)
		p2 = []
		pathtoNode(root, p2, b)
		i = 0
		while i < len(p1) and i < len(p2):
			if p1[i] != p2[i]:
				break
			i += 1
		return len(p1) - i + len(p2) - i


class Solution:

	def findLCS(self, root, a, b):
		if root == None:
			return root
		if root.data == a or root.data == b:
			return root
		left = self.findLCS(root.left, a, b)
		right = self.findLCS(root.right, a, b)
		if left != None and right != None:
			return root
		if left != None:
			return left
		return right

	def findDistUtils(self, node, val):
		if node == None:
			return 0
		if node.data == val:
			return 1
		left_val = self.findDistUtils(node.left, val)
		right_val = self.findDistUtils(node.right, val)
		if left_val == 0 and right_val == 0:
			return 0
		return left_val + right_val + 1

	def findDist(self, root, a, b):
		lcs = self.findLCS(root, a, b)
		return self.findDistUtils(lcs, a) + self.findDistUtils(lcs, b) - 2


def pathToNode(root, path, k):
	if root is None:
		return False
	path.append(root.data)
	if root.data == k:
		return True
	if root.left != None and pathToNode(root.left, path, k) or (root.right != None and pathToNode(root.right, path, k)):
		return True
	path.pop()
	return False

class Solution:

	def findDist(self, root, data1, data2):
		if root:
			path1 = []
			pathToNode(root, path1, data1)
			path2 = []
			pathToNode(root, path2, data2)
			i = 0
			while i < len(path1) and i < len(path2):
				if path1[i] != path2[i]:
					break
				i = i + 1
			return len(path1) + len(path2) - 2 * i
		else:
			return 0


from collections import deque

class Solution:

	def __init__(self):
		self.la = ''
		self.lb = ''

	def findDist(self, root, a, b):
		if root == None:
			return 0
		q = deque([root])
		while len(q) != 0:
			x = q.popleft()
			if x == root:
				x.data = [x.data, '']
			if x.data[0] == a:
				self.la = x.data[1]
			if x.data[0] == b:
				self.lb = x.data[1]
			if x.left:
				x.left.data = [x.left.data, x.data[1] + 'l']
				q.append(x.left)
			if x.right:
				x.right.data = [x.right.data, x.data[1] + 'r']
				q.append(x.right)
		(q, r) = (len(self.la), len(self.lb))
		n = min(q, r)
		for i in range(n):
			if self.la[i] == self.lb[i]:
				q -= 1
				r -= 1
			else:
				break
		return q + r


class Solution:

	def findDist(self, root, a, b):

		def travers(root, vals, target):
			if root == None:
				return
			vals.append(root.data)
			if root.data == target:
				final.append(vals.copy())
				return
			travers(root.left, vals, target)
			travers(root.right, vals, target)
			vals.pop()
		final = []
		travers(root, [], a)
		travers(root, [], b)
		path_1 = final[0]
		path_2 = final[1]
		i = 0
		while i < len(path_1) and i < len(path_2) and (path_1[i] == path_2[i]):
			i += 1
		lca = path_1[i - 1]
		travers(root, [], lca)
		return len(final[0]) + len(final[1]) - 2 * len(final[2])


class Solution:

	def findDist(self, root, n1, n2):
		lca_node = self.lca(root, n1, n2)
		n1_dist = self.distance_from_lca(lca_node, n1)
		n2_dist = self.distance_from_lca(lca_node, n2)
		return n1_dist + n2_dist - 2

	def distance_from_lca(self, root, value: int):
		if root is None:
			return 0
		if root.data == value:
			return 1
		left_check = self.distance_from_lca(root.left, value)
		right_check = self.distance_from_lca(root.right, value)
		if left_check == 0 and right_check == 0:
			return 0
		return left_check + right_check + 1

	def lca(self, root, n1: int, n2: int):
		if root is None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		left_check = self.lca(root.left, n1, n2)
		right_check = self.lca(root.right, n1, n2)
		if left_check is not None and right_check is not None:
			return root
		elif left_check is None:
			return right_check
		else:
			return left_check


import collections

class Solution:

	def findLCA(self, root, a, b):
		a_path = self.findPath(root, a)
		b_path = self.findPath(root, b)
		a_set = set(a_path)
		b_set = set(b_path)
		ances_nodes = a_set.intersection(b_set)
		for i in range(len(b_path) - 1, -1, -1):
			if b_path[i] in ances_nodes:
				return b_path[i]

	def findPath(self, root, a):
		q = collections.deque()
		q.append((root, [root]))
		while len(q):
			(curr_node, curr_path) = q.popleft()
			if curr_node.data == a:
				return curr_path
			tmp_path = curr_path[:]
			if curr_node.left:
				tmp_path.append(curr_node.left)
				q.append((curr_node.left, tmp_path))
			tmp_path2 = curr_path[:]
			if curr_node.right:
				tmp_path2.append(curr_node.right)
				q.append((curr_node.right, tmp_path2))

	def findDist(self, root, a, b):
		lca = self.findLCA(root, a, b)
		a_path = self.findPath(lca, a)
		b_path = self.findPath(lca, b)
		return len(a_path) + len(b_path) - 2


class Solution:

	def findDist(self, root, a, b):

		def findLCA(node, a, b):
			if not node:
				return
			if node.data == a or node.data == b:
				return node
			leftLCA = findLCA(node.left, a, b)
			rightLCA = findLCA(node.right, a, b)
			if leftLCA and rightLCA:
				return node
			if leftLCA:
				return leftLCA
			if rightLCA:
				return rightLCA
		LCA = findLCA(root, a, b)

		def findDist(node, value, dist):
			if not node:
				return -1
			if node.data == value:
				return dist
			d = findDist(node.left, value, dist + 1)
			if d != -1:
				return d
			else:
				return findDist(node.right, value, dist + 1)
		d1 = findDist(LCA, a, 0)
		d2 = findDist(LCA, b, 0)
		return d1 + d2


class Solution:

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

	def mindist(self, root, val):
		if not root:
			return float('inf')
		if root.data == val:
			return 0
		lh = self.mindist(root.left, val)
		rh = self.mindist(root.right, val)
		return 1 + min(lh, rh)

	def findDist(self, root, a, b):
		parent = self.lca(root, a, b)
		a_dist = self.mindist(parent, a)
		b_dist = self.mindist(parent, b)
		return a_dist + b_dist


class Solution:

	def findDist(self, root, a, b):
		lca_node = self.LCA(root, a, b)
		d1 = self.Distance(lca_node, a)
		d2 = self.Distance(lca_node, b)
		return d1 + d2 - 2

	def LCA(self, root, a, b):
		if not root:
			return None
		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
		elif l is None:
			return r
		else:
			return l

	def Distance(self, root, val):
		if not root:
			return 0
		if root.data == val:
			return 1
		x = self.Distance(root.left, val)
		y = self.Distance(root.right, val)
		if not x and (not y):
			return 0
		else:
			return x + y + 1


class Solution:

	def findDist(self, root, a, b):
		both = [0]

		def findmin(root, a, b):
			if root == None:
				return 999999999
			if root.data == a and root.data == b:
				both[0] = 1
				return 0
			ans = 999999999
			if root.data == a or root.data == b:
				ans = min(ans, 1)
			left = findmin(root.left, a, b)
			right = findmin(root.right, a, b)
			if left == 0 or right == 0:
				both[0] = 1
				return 0
			if left != 999999999 and right != 999999999:
				both[0] = 1
				return left + right
			if ans != 999999999 and left != 999999999:
				both[0] = 1
				return left
			if ans != 999999999 and right != 999999999:
				both[0] = 1
				return right
			if ans == 999999999 and left != 999999999:
				if both[0] == 0:
					return left + 1
				else:
					return left
			if ans == 999999999 and right != 999999999:
				if both[0] == 0:
					return 1 + right
				else:
					return right
			return ans
		return findmin(root, a, b)


class Solution:

	def getlca(self, root, x1, x2):
		if root is None:
			return None
		if root.data == x1 or root.data == x2:
			return root
		left = self.getlca(root.left, x1, x2)
		right = self.getlca(root.right, x1, x2)
		if left != None and right != None:
			return root
		if left != None and right is None:
			return left
		return right

	def getheight(self, root, val, dist):
		if root is None:
			return -1
		if root.data == val:
			return dist
		l = self.getheight(root.left, val, dist + 1)
		if l != -1:
			return l
		return self.getheight(root.right, val, dist + 1)

	def findDist(self, root, a, b):
		lca = self.getlca(root, a, b)
		d1 = self.getheight(lca, a, 0)
		d2 = self.getheight(lca, b, 0)
		return d1 + d2


class Solution:

	def findDist(self, root, a, b):

		def lcs(root):
			if root == None or root.data == a or root.data == b:
				return root
			l = lcs(root.left)
			r = lcs(root.right)
			if l and r:
				return root
			return l if l else r
		self.l1 = []

		def depth(root, d, ele):
			if root == None:
				return False
			if root.data == ele:
				self.l1.append(d)
				return True
			if depth(root.left, d + 1, ele):
				return True
			if depth(root.right, d + 1, ele):
				return True
			return False
		r = lcs(root)
		depth(r, 0, a)
		depth(r, 0, b)
		return self.l1[0] + self.l1[1]


class Solution(object):

	def findDist(self, root, a, b):
		if a == b:
			return 0
		lca = self.LCA(root, a, b)
		if lca is None:
			return -1
		dist1 = self.distanceToNode(lca, a, 0)
		dist2 = self.distanceToNode(lca, b, 0)
		return dist1 + dist2

	def LCA(self, node, a, b):
		if not node:
			return None
		if node.data == a or node.data == b:
			return node
		left = self.LCA(node.left, a, b)
		right = self.LCA(node.right, a, b)
		if left and right:
			return node
		elif left:
			return left
		else:
			return right

	def distanceToNode(self, node, target, distance):
		if not node:
			return 0
		if node.data == target:
			return distance
		return self.distanceToNode(node.left, target, distance + 1) or self.distanceToNode(node.right, target, distance + 1)


class Solution:

	def findDist(self, root, a, b):

		def lowest(root):
			if not root:
				return None
			if root.data == a or root.data == b:
				return root
			l = lowest(root.left)
			r = lowest(root.right)
			if l != None and r != None:
				return root
			else:
				return l or r

		def diste(lca, x, dist):
			if lca is None:
				return 0
			if lca.data == x:
				return dist
			left = diste(lca.left, x, dist + 1)
			if left != 0:
				return left
			return diste(lca.right, x, dist + 1)
		fin = lowest(root)
		x = diste(fin, a, 0)
		y = diste(fin, b, 0)
		return x + y


class Solution:

	def lca(self, root, a, b):
		if root == None:
			return None
		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 != None and r != None:
			return root
		elif l != None:
			return l
		else:
			return r

	def solve(self, root, x):
		if root == None:
			return 0
		if root.data == x:
			return 1
		l = self.solve(root.left, x)
		r = self.solve(root.right, x)
		if l == 0 and r == 0:
			return 0
		else:
			return l + r + 1

	def findDist(self, root, a, b):
		LCA = self.lca(root, a, b)
		d1 = self.solve(LCA, a)
		d2 = self.solve(LCA, b)
		return d1 + d2 - 2


class Solution:

	def store(self, root, ancestor):
		if root is None:
			return
		try:
			self.d[root.data] = self.d[root.data] + ancestor
		except:
			self.d[root.data] = ancestor + [root.data]
		self.store(root.left, ancestor + [root.data])
		self.store(root.right, ancestor + [root.data])

	def findDist(self, root, a, b):
		self.d = {}
		common_list = []
		lowest_common_ancestor = None
		self.store(root, [])
		a_ancestor = self.d[a][::-1]
		b_ancestor = self.d[b]
		for iterator in a_ancestor:
			if iterator in b_ancestor:
				lowest_common_ancestor = iterator
				break
		for i in range(0, len(a_ancestor)):
			if a_ancestor[i] != lowest_common_ancestor:
				common_list.append(a_ancestor[i])
			else:
				break
		for j in range(0, len(b_ancestor)):
			if b_ancestor[j] == lowest_common_ancestor:
				common_list.extend(b_ancestor[j:])
				break
		position = {}
		for k in range(0, len(common_list)):
			position[common_list[k]] = k
		return abs(position[b] - position[a])


class Solution:
	co = 0

	def lca(self, root, a, b):
		if root == None:
			return
		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 != None and r != None:
			return root
		elif l == None and r != None:
			return r
		elif l != None and r == None:
			return l
		else:
			return None

	def dis(self, root, n, l):
		if root == None:
			return 0
		if root.data == n:
			self.co += l
		self.dis(root.left, n, l + 1)
		self.dis(root.right, n, l + 1)

	def findDist(self, root, a, b):
		if root == None:
			return None
		ans = self.lca(root, a, b)
		self.dis(ans, a, 0)
		self.dis(ans, b, 0)
		return self.co


class Solution:

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

	def MinDistance(self, root, a, b):
		if root == None:
			return 0
		left = self.MinDistance(root.left, a, b)
		right = self.MinDistance(root.right, a, b)
		if root.data == a or root.data == b:
			if left != 0:
				self.ans = left
			elif right != 0:
				self.ans = right
			return 1
		if left != 0 and right != 0:
			self.ans = left + right
			return 0
		elif left != 0:
			return left + 1
		elif right != 0:
			return right + 1
		else:
			return 0

	def findDist(self, root, a, b):
		if a == b:
			return 0
		self.ans = -1
		self.MinDistance(root, a, b)
		return self.ans


class Solution:

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

	def dist(self, root, a):
		if root is None:
			return -1
		if root.data == a:
			return 0
		left_dist = self.dist(root.left, a)
		right_dist = self.dist(root.right, a)
		if left_dist == -1 and right_dist == -1:
			return -1
		return 1 + max(left_dist, right_dist)

	def findDist(self, root, a, b):
		temp = self.lca(root, a, b)
		dist_a = self.dist(temp, a)
		dist_b = self.dist(temp, b)
		return dist_a + dist_b


def func(root, parent, gr):
	if root is None:
		return
	if parent != -1:
		if parent not in gr:
			gr[parent] = [root.data]
		elif parent in gr:
			gr[parent].append(root.data)
		if root.data not in gr:
			gr[root.data] = [parent]
		elif root.data in parent:
			gr[root.data].append(parent)
	func(root.left, root.data, gr)
	func(root.right, root.data, gr)

class Solution:

	def findDist(self, root, a, b):
		if root.right is None and root.left is None:
			return 0
		gr = {}
		func(root, -1, gr)
		dist = {i: float('inf') for i in gr}
		dist[a] = 0
		q = [a]
		while q:
			cur = q.pop(0)
			for i in gr[cur]:
				if dist[i] > dist[cur] + 1:
					dist[i] = dist[cur] + 1
					q.append(i)
		return dist[b]


class Solution:

	def find(self, root, path1, k):
		if root is None:
			return False
		path1.append(root.data)
		if root.data == k:
			return True
		if root.left != None and self.find(root.left, path1, k) or (root.right != None and self.find(root.right, path1, k)):
			return True
		path1.pop()
		return False

	def findDist(self, root, a, b):
		path1 = []
		self.find(root, path1, a)
		path2 = []
		self.find(root, path2, b)
		i = 0
		while i < len(path1) and i < len(path2):
			if path1[i] != path2[i]:
				break
			i = i + 1
		return len(path1) + len(path2) - 2 * i


class Solution:

	def find_lca(self, root, a, b):
		if root == None:
			return
		if root.data in (a, b):
			return root
		left_ans = self.find_lca(root.left, a, b)
		right_ans = self.find_lca(root.right, a, b)
		if left_ans and right_ans:
			return root
		return left_ans or right_ans

	def find_distance_from_node(self, root, value):
		if root == None:
			return
		if root.data == value:
			return 1
		left_ans = self.find_distance_from_node(root.left, value)
		right_ans = self.find_distance_from_node(root.right, value)
		if left_ans or right_ans:
			return (left_ans or right_ans) + 1
		else:
			return left_ans or right_ans

	def findDist(self, root, a, b):
		if a == b:
			return 0
		lca = self.find_lca(root, a, b)
		a_dist = self.find_distance_from_node(lca, a)
		b_dist = self.find_distance_from_node(lca, b)
		return a_dist + b_dist - 2


class Solution:

	def find_lca(self, root, a, b):
		if root == None:
			return
		if root.data in (a, b):
			return root.data
		left_ans = self.find_lca(root.left, a, b)
		right_ans = self.find_lca(root.right, a, b)
		if left_ans and right_ans:
			return root.data
		return left_ans or right_ans

	def find_distance_from_node(self, root, node, value, ans):
		if root == None:
			return
		if root.data == value:
			return 1
		left_ans = self.find_distance_from_node(root.left, node, value, ans)
		right_ans = self.find_distance_from_node(root.right, node, value, ans)
		if left_ans or right_ans:
			if root.data == node:
				ans[0] = left_ans or right_ans
			return (left_ans or right_ans) + 1
		else:
			return left_ans or right_ans

	def findDist(self, root, a, b):
		if a == b:
			return 0
		lca = self.find_lca(root, a, b)
		ans_a = [0]
		self.find_distance_from_node(root, lca, a, ans_a)
		ans_b = [0]
		self.find_distance_from_node(root, lca, b, ans_b)
		return ans_a[0] + ans_b[0]


class Solution:
	dist = 0

	def findDist(self, root, a, b):
		p = self.lca(root, a, b)
		self.find(p, a, 0)
		self.find(p, b, 0)
		return self.dist

	def lca(self, root, a, b):
		if root == None or root.data == a or root.data == b:
			return root
		left = self.lca(root.left, a, b)
		right = self.lca(root.right, a, b)
		if left and right:
			return root
		elif left:
			return left
		else:
			return right

	def find(self, root, n, level):
		if root == None:
			return 0
		if root.data == n:
			self.dist += level
			return level
		self.find(root.left, n, level + 1)
		self.find(root.right, n, level + 1)


class Solution:

	def LCA(self, root, a, b):
		if root is None:
			return None
		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 != None and r != None:
			return root
		elif l != None and r == None:
			return l
		elif r != None and l == None:
			return r

	def solve(self, root, x):
		if root is None:
			return 0
		if root.data == x:
			return 1
		a = self.solve(root.left, x)
		b = self.solve(root.right, x)
		if a == 0 and b == 0:
			return 0
		return a + b + 1

	def findDist(self, root, a, b):
		lca = self.LCA(root, a, b)
		x = self.solve(lca, a)
		y = self.solve(lca, b)
		return x + y - 2


class Solution:
	lvl = 0

	def dist(self, root, k, c):
		if not root:
			return 0
		if root.data == k:
			self.lvl = self.lvl + c
			return c
		self.dist(root.left, k, c + 1)
		self.dist(root.right, k, c + 1)

	def lca(self, root, a, b):
		if root is None or root.data == a or root.data == b:
			return root
		lr = self.lca(root.left, a, b)
		rr = self.lca(root.right, a, b)
		if lr == None:
			return rr
		if rr == None:
			return lr
		return root

	def findDist(self, root, a, b):
		lcan = self.lca(root, a, b)
		(k1, k2) = (0, 0)
		k1 = self.dist(lcan, a, 0)
		k2 = self.dist(lcan, b, 0)
		return self.lvl


class Solution:

	def findDist(self, root, a, b):
		(x, y) = ([], [])

		def manu(root, ans, p):
			if root is None:
				return False
			ans.append(root.data)
			if root.data == p:
				return True
			if manu(root.left, ans, p) or manu(root.right, ans, p):
				return True
			ans.pop()
			return
		manu(root, x, a)
		manu(root, y, b)
		i = 0
		k = min(len(x), len(y))
		while i < k - 1:
			if x[0] == y[0] and x[1] == y[1]:
				x.pop(0)
				y.pop(0)
			else:
				break
			i += 1
		return len(x) + len(y) - 2


class Solution:

	def findDist(self, root, a, b):
		if a == b:
			return 0
		(path1, path2) = self.helper(root, [], a, b)
		while path1 and path2 and (path1[-1] == path2[-1]):
			path1.pop()
			path2.pop()
		return len(path1 + path2)

	def helper(self, root, path, a, b):
		if root is None:
			return []
		output = []
		if root.data == a or root.data == b:
			output.append(path.copy())
		output += self.helper(root.left, [0] + path.copy(), a, b)
		output += self.helper(root.right, [1] + path.copy(), a, b)
		return output


class Solution:

	def findDist(self, root, n1, n2):
		l11 = []
		l12 = []
		t1 = []
		t2 = []
		nm(root, n1, l11 + [root.data], t1)
		nm(root, n2, l12 + [root.data], t2)
		l11 = t1
		l12 = t2
		l11 = l11[-1::-1]
		l12 = l12[-1::-1]
		if len(l11) >= len(l12):
			for i in range(len(l11)):
				if l11[i] in l12:
					o = l11[i]
					break
		else:
			for i in range(len(l12)):
				if l12[i] in l11:
					o = l12[i]
					break
		gap = 0
		a = l11
		for i in a:
			if i != o:
				gap += 1
			else:
				break
		for i in l12:
			if i != o:
				gap += 1
			else:
				break
		return gap
import copy

def nm(root, n1, l1, t):
	if root.data == n1:
		t.extend(copy.deepcopy(l1))
	if root.left:
		nm(root.left, n1, l1 + [root.left.data], t)
	if root.right:
		nm(root.right, n1, l1 + [root.right.data], t)


class Solution:

	def solve(self, root, a, b):
		if not root:
			return [None, None, 0, 0]
		if not root.left and (not root.right):
			if root.data == a:
				return [root.data, None, 1, 0]
			if root.data == b:
				return [None, root.data, 1, 0]
			return [None, None, 1, 0]
		l = self.solve(root.left, a, b)
		r = self.solve(root.right, a, b)
		if l[3] != 0:
			return l
		if r[3] != 0:
			return r
		(status1, status2) = (False, False)
		(cnt1, cnt2) = (0, 0)
		(first, second, height) = (None, None, 0)
		if l[0] == a or r[0] == a:
			cnt1 = l[2] if l[0] == a else r[2]
			first = a
			status1 = True
			height = cnt1
		if l[1] == b or r[1] == b:
			second = b
			cnt2 = l[2] if l[1] == b else r[2]
			status2 = True
			height = cnt2
		if status1 and status2:
			height = cnt1 + cnt2
		res = [first, second, height, 0]
		if res[0] == a and res[1] == b:
			res[3] = height
			return res
		if root.data == a:
			res[0] = root.data
		if root.data == b:
			res[1] = root.data
		if res[0] == a and res[1] == b:
			res[3] = height
			return res
		if res[0] == a or res[1] == b:
			res[2] += 1
		return res

	def findDist(self, root, a, b):
		return self.solve(root, a, b)[3]


class Solution:

	def findDist(self, root, a, b):

		def path(root, n, ans1):
			if root == None:
				return False
			ans1.append(root.data)
			if root.data == n:
				return True
			if path(root.left, n, ans1) or path(root.right, n, ans1):
				return True
			ans1.pop()
			return False
		ans1 = []
		ans2 = []
		path(root, a, ans1)
		path(root, b, ans2)
		main = []
		for i in range(len(ans2)):
			if ans2[i] not in ans1:
				main.append(ans2[i])
		for i in range(len(ans1)):
			if ans1[i] not in ans2 and ans1[i] not in main:
				main.append(ans1[i])
		return len(main)


def dim(root, a, path):
	if not root:
		return False
	path.append(root.data)
	if root.data == a:
		return True
	if root.left != None and dim(root.left, a, path) or (root.right != None and dim(root.right, a, path)):
		return True
	path.pop()
	return False

class Solution:

	def findDist(self, root, a, b):
		if root:
			path1 = []
			dim(root, a, path1)
			path2 = []
			dim(root, b, path2)
			i = 0
			while i < len(path1) and i < len(path2):
				if path1[i] != path2[i]:
					break
				i += 1
			return len(path1) + len(path2) - 2 * i
		else:
			return 0


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

def findDis(root, a):
	if root == None:
		return -1
	if root.data == a:
		return 0
	l = findDis(root.left, a)
	r = findDis(root.right, a)
	if l == -1 and r == -1:
		return -1
	else:
		return max(l, r) + 1

class Solution:

	def findDist(self, root, a, b):
		comm = lca(root, a, b)
		m = findDis(comm, a)
		n = findDis(comm, b)
		return m + n


class Solution:

	def getpath(self, root, val, path):
		if root == None:
			return False
		path.append(root.data)
		if root.data == val:
			return True
		if self.getpath(root.left, val, path) or self.getpath(root.right, val, path):
			return True
		path.pop()
		return False

	def findDist(self, root, a, b):
		path1 = []
		path2 = []
		self.getpath(root, a, path1)
		self.getpath(root, b, path2)
		while path1 and path2 and (path1[0] == path2[0]):
			path1.pop(0)
			path2.pop(0)
		return len(path1) + len(path2)


class Solution:

	def lca(self, root, a, b):
		if root is None:
			return None
		if root.data == a or root.data == b:
			return root
		leftAns = self.lca(root.left, a, b)
		rightAns = self.lca(root.right, a, b)
		if leftAns and (not rightAns):
			return leftAns
		elif leftAns and rightAns:
			return root
		elif not leftAns and rightAns:
			return rightAns
		else:
			return None

	def solve(self, root, x):
		if root is None:
			return float('inf')
		if root.data == x:
			return 0
		left = 1 + self.solve(root.left, x)
		right = 1 + self.solve(root.right, x)
		return min(left, right)

	def findDist(self, root, a, b):
		node = self.lca(root, a, b)
		if node is None:
			return 0
		return self.solve(node, a) + self.solve(node, b)


class Solution:

	def findDist(self, root, n1, n2):
		lca = self.findLCA(root, n1, n2)
		d1 = self.findLevel(lca, n1, 0)
		d2 = self.findLevel(lca, n2, 0)
		return d1 + d2

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

	def findLevel(self, root, k, level):
		if root is None:
			return -1
		if root.data == k:
			return level
		left_level = self.findLevel(root.left, k, level + 1)
		if left_level == -1:
			return self.findLevel(root.right, k, level + 1)
		return left_level


class Solution:

	def findDist(self, root, a, b):

		def findNode(root, a):
			if not root:
				return (False, [])
			if root.data == a:
				return (True, [root.data])
			(in_right, stack_right) = findNode(root.right, a)
			(in_left, stack_left) = findNode(root.left, a)
			if in_right:
				return (True, [root.data] + stack_right)
			if in_left:
				return (True, [root.data] + stack_left)
			return (False, [])
		(i, j) = (0, 0)
		left = findNode(root, a)[1]
		right = findNode(root, b)[1]
		(n, m) = (len(left), len(right))
		while i < n and j < m:
			if left[i] != right[j]:
				break
			i += 1
			j += 1
		return n - i + m - j


class Solution:

	def findDist(self, root, a, b):

		def lca(root, a, b):
			if root == None or root.data == a or root.data == b:
				return root
			left = lca(root.left, a, b)
			right = lca(root.right, a, b)
			if left == None:
				return right
			if right == None:
				return left
			else:
				return root

		def path(root, a, arr):
			if not root:
				return False
			arr.append(root.data)
			if root.data == a:
				return True
			if path(root.left, a, arr) or path(root.right, a, arr):
				return True
			arr.pop()
			return False
		arr2 = []
		arr1 = []
		common = lca(root, a, b)
		path(common, a, arr1)
		path(common, b, arr2)
		return len(arr2) + len(arr1) - 2


class Solution:

	def findDist(self, root, a, b):

		def findLCA(root, n1, n2):
			if root is None:
				return None
			if root.data == n1 or root.data == n2:
				return root
			left_lca = findLCA(root.left, n1, n2)
			right_lca = findLCA(root.right, n1, n2)
			if left_lca and right_lca:
				return root
			return left_lca if left_lca else right_lca

		def height(root, n1, n2, ht):
			if root == None:
				return 0
			if root.data == n1:
				ans[0] = ht
			if root.data == n2:
				ans[1] = ht
			height(root.left, n1, n2, ht + 1)
			height(root.right, n1, n2, ht + 1)
		LCA = findLCA(root, a, b)
		ans = [0, 0]
		height(LCA, a, b, 0)
		return sum(ans)


class Solution:

	def solve(self, root, a, b):
		if root == None:
			return None
		if root.data == a or root.data == b:
			return root
		leftans = self.solve(root.left, a, b)
		rightans = self.solve(root.right, a, b)
		if leftans != None and rightans != None:
			return root
		elif leftans == None and rightans != None:
			return rightans
		elif rightans == None and leftans != None:
			return leftans
		else:
			return None

	def solve1(self, root, val):
		if root == None:
			return 0
		if root.data == val:
			return 1
		a = self.solve1(root.left, val)
		b = self.solve1(root.right, val)
		if a == 0 and b == 0:
			return 0
		else:
			return a + b + 1

	def findDist(self, root, a, b):
		LCA = self.solve(root, a, b)
		x = self.solve1(LCA, a)
		y = self.solve1(LCA, b)
		return x + y - 2


class Solution:

	def lca(self, root, n1, n2):
		if root == None:
			return root
		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 and r:
			return root
		return l or r

	def solve(self, root, x):
		if root == None:
			return 0
		if root.data == x:
			return 1
		left = self.solve(root.left, x)
		right = self.solve(root.right, x)
		if not left and (not right):
			return 0
		else:
			return left + right + 1

	def findDist(self, root, a, b):
		lca = self.lca(root, a, b)
		x = self.solve(lca, a)
		y = self.solve(lca, b)
		return x + y - 2


class Solution:

	def lca(self, root, a, b):
		if root == None:
			return None
		if root.data == a or root.data == b:
			return root
		lans = self.lca(root.left, a, b)
		rans = self.lca(root.right, a, b)
		if lans != None and rans == None:
			return lans
		if rans != None and lans == None:
			return rans
		if lans != None and rans != None:
			return root
		else:
			return None

	def solve(self, root, x):
		if root == None:
			return -1
		if root.data == x:
			return 0
		left = self.solve(root.left, x)
		right = self.solve(root.right, x)
		distance = max(left, right)
		if distance >= 0:
			return distance + 1
		else:
			return -1

	def findDist(self, root, a, b):
		lca = self.lca(root, a, b)
		x = self.solve(lca, a)
		y = self.solve(lca, b)
		return x + y


class Solution:

	def findDist(self, root, a, b):

		def func(root, a, li, ans):
			if root is None:
				return
			li.append(root.data)
			if root.data == a:
				return True
			if func(root.left, a, li, ans) or func(root.right, a, li, ans):
				return True
			li.pop()
			return False
		li = []
		ans = []
		func(root, a, li, ans)
		li2 = []
		func(root, b, li2, ans)
		leni = len(li) + len(li2)
		minius = 0
		for i in range(min(len(li), len(li2))):
			if li[i] == li2[i]:
				minius += 2
			else:
				break
		return leni - minius


class Solution:

	def findDist(self, root, a, b):
		ans = [-1]
		self.findNode(root, a, ans)
		par = {}
		self.makeParent(root, par)
		return self.bfs(ans[0], b, par)

	def makeParent(self, root, d):
		q = [root]
		while q:
			n = q.pop(0)
			if n.left:
				d[n.left] = n
				q.append(n.left)
			if n.right:
				d[n.right] = n
				q.append(n.right)

	def findNode(self, root, a, ans):
		if root == None:
			return
		self.findNode(root.left, a, ans)
		if root.data == a:
			ans[0] = root
			return
		self.findNode(root.right, a, ans)

	def bfs(self, root, b, par):
		vis = {}
		q = []
		q.append([root, 0])
		vis[root] = True
		while q:
			n = q.pop(0)
			rt = n[0]
			step = n[1]
			if rt.data == b:
				return step
			if rt.left and rt.left not in vis:
				q.append([rt.left, step + 1])
				vis[rt.left] = True
			if rt.right and rt.right not in vis:
				q.append([rt.right, step + 1])
				vis[rt.right] = True
			if par.get(rt) != None and par[rt] not in vis:
				q.append([par[rt], step + 1])
				vis[par[rt]] = True
		return -1