Given a binary tree. The task is to find the Node with maximum GCD of the siblings of this tree. You have to return the value of the node whose two immediate children has the maximum gcd.
If there are multiple such nodes, return the node which has the maximum value.
Siblings: Nodes with the same parent are called siblings.
GCD (Greatest Common Divisor) of two positive integers is the largest positive integer that divides both numbers without a remainder.
Note:
Consider those nodes which have a sibling.
Return 0 if no such pair of siblings found.
 
Example 1:
Input:
              4
            /   \
           5     2
                /  \
               3    1
              /  \
             6   12
Output: 3
Explanation: For the above tree, the maximum
GCD for the siblings is formed for nodes 6 and 12
for the children of node 3.
 
Example 2:
Input: 
            1
          /   \
        3      5
      /  \    /  \
     6    9  4    8
Output: 5
Explanation: For the above tree, the maximum
GCD for the siblings is formed for nodes 4 and 8
for the children of node 5.
 
Your Task:
You don't need to take input. Just complete the function maxGCD() that takes the root node as a parameter and returns the value of the node whose two immediate children has the maximum gcd.
 
Expected Time Complexity: O(|Number of nodes|) .
Expected Auxiliary Space: O(height of the tree) .
 
Constraints:
1 <= Number of nodes <= 10^{5}
1 <= Data of a node <= 10^{5}

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|Number of nodes|) .
Expected Auxiliary Space: O(height of the tree) .

Starter code:
'''

# Node Class:

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

        '''

class Solution:

    def maxGCD(self, root):

        # code here

Solutions:
class Solution:

	def maxGCD(self, root):
		q = [root]
		max_g = 0
		max_n = 0
		import math
		while q:
			l = len(q)
			for i in range(l):
				p = q.pop(0)
				if p.left and p.right:
					gc = math.gcd(p.left.data, p.right.data)
					if gc > max_g:
						max_g = gc
						max_n = p.data
					elif gc == max_g:
						if p.data > max_n:
							max_g = gc
							max_n = p.data
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
		return max_n


class Solution:

	def fun(self, root, d, res):
		if root == None:
			return
		if root.left and root.right:
			d1 = root.left.data
			d2 = root.right.data
			while d1 != d2:
				if d1 > d2:
					d1 -= d2
				else:
					d2 -= d1
			if d2 > d[0]:
				d[0] = d2
				res.append(root)
			elif d2 == d[0]:
				t = res[-1].data
				if root.data > t:
					res.append(root)
		self.fun(root.left, d, res)
		self.fun(root.right, d, res)

	def maxGCD(self, root):
		d = [0]
		res = []
		self.fun(root, d, res)
		if len(res) == 0:
			return 0
		return res[-1].data


import math

class Solution:

	def solve(self, root, res, temp):
		if root == None:
			return
		if root.left and root.right:
			k = math.gcd(root.left.data, root.right.data)
			if k > self.temp:
				self.temp = k
				self.res = root.data
			if k == self.temp and self.res < root.data:
				self.res = root.data
		self.solve(root.left, res, temp)
		self.solve(root.right, res, temp)

	def maxGCD(self, root):
		dic = {}
		self.res = 0
		self.temp = float('-inf')
		self.solve(root, 0, 0)
		return self.res


class Solution:

	def maxGCD(self, root):
		self.max_val = float('-inf')
		self.ans = 0

		def dfs(node):
			if not node:
				return 0
			if not node.left and (not node.right):
				return 0
			if node.left and node.right:
				val = findGCF(node.left.data, node.right.data)
				if self.max_val < val:
					self.max_val = val
					self.ans = node.data
				elif self.max_val == val and self.ans < node.data:
					self.ans = node.data
			dfs(node.left)
			dfs(node.right)

		def findGCF(a, b):
			if b == 0:
				return a
			return findGCF(b, a % b)
		dfs(root)
		return self.ans


from math import gcd

class Solution:

	def maxGCD(self, root):
		return self.helper(root)[1]

	def helper(self, root):
		if root is None:
			return (0, 0)
		left = self.helper(root.left)
		right = self.helper(root.right)
		current = (0, 0)
		if root.left and root.right:
			current = (gcd(root.left.data, root.right.data), root.data)
		return max(left, right, current)


class Solution:

	def maxGCD(self, root):

		def gcd(a, b):
			if a == 0:
				return b
			return gcd(b % a, a)

		def helper(root):
			ans = []
			if not root:
				return ans
			ans += helper(root.left)
			ans.append(root)
			ans += helper(root.right)
			return ans
		a = helper(root)
		ans = 0
		x = 0
		for i in a:
			if i.left != None and i.right != None:
				c = gcd(i.left.data, i.right.data)
				if c > x:
					ans = i.data
					x = c
		return ans


import math

class Solution:

	def gcdSibling(self, root, gcd, maxData):
		if root == None:
			return 0
		if root.left != None and root.right != None:
			gcdCurr = math.gcd(root.left.data, root.right.data)
			if gcd[0] < gcdCurr:
				maxData[0] = root.data
				gcd[0] = gcdCurr
			elif gcd[0] == gcdCurr:
				if maxData[0] < root.data:
					maxData[0] = root.data
		self.gcdSibling(root.left, gcd, maxData)
		self.gcdSibling(root.right, gcd, maxData)

	def maxGCD(self, root):
		gcd = [0]
		maxData = [0]
		self.gcdSibling(root, gcd, maxData)
		return maxData[0]


from math import gcd

class Solution:

	def maxGCD(self, root):
		return self.solve(root)[1]

	def solve(self, node):
		if node is None:
			return (0, 0)
		x = (0, 0)
		if node.left and node.right:
			x = (gcd(node.left.data, node.right.data), node.data)
		y = self.solve(node.left)
		z = self.solve(node.right)
		return max(x, y, z)


import math

class Solution:
	answer = 0
	tmp1 = 0

	def search(self, root):
		if root is not None:
			left = self.search(root.left)
			right = self.search(root.right)
			if left == 0 or right == 0:
				tmp = 0
			else:
				tmp = math.gcd(left, right)
			if self.tmp1 < tmp:
				self.tmp1 = tmp
				self.answer = root.data
			return root.data
		else:
			return 0

	def maxGCD(self, root):
		self.search(root)
		return self.answer


import math

class Solution:

	def helper(self, node):
		q = [node]
		while q:
			nq = []
			for i in q:
				if i.left and i.right:
					val = math.gcd(i.left.data, i.right.data)
					if self.gcd <= val:
						(self.gcd, self.res) = (val, i.data)
				if i.left:
					nq.append(i.left)
				if i.right:
					nq.append(i.right)
			q = nq

	def maxGCD(self, root):
		if root is None:
			return -1
		(self.gcd, self.res) = (float('-inf'), 0)
		self.helper(root)
		return self.res


import math

class Solution:

	def __init__(self):
		self.minn = 0
		self.prev = 0

	def max_gcd(self, root):
		if root != None:
			self.max_gcd(root.left)
			if root.left != None:
				left = root.left.data
			self.max_gcd(root.right)
			if root.right != None:
				right = root.right.data
			if root.left != None and root.right != None:
				cal_gcd = math.gcd(left, right)
				if cal_gcd > self.prev:
					self.minn = root.data
					self.prev = cal_gcd
				elif cal_gcd == self.prev:
					self.minn = max(self.minn, root.data)

	def maxGCD(self, root):
		if root == None:
			return 0
		self.max_gcd(root)
		return self.minn


import math

class Solution:

	def maxGCD(self, root):
		q = [root]
		ans = 0
		res = {}
		re = []
		while q:
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			if node.left and node.right:
				k = math.gcd(node.left.data, node.right.data)
				res[k] = node.data
				re.append(k)
		if re:
			return res[max(re)]
		return 0


class Solution:

	def maxGCD(self, root):

		def gdc(a, b):
			if b == 0:
				return a
			return gdc(b, a % b)
		l = []
		q = []
		q.append(root)
		while q:
			x = q.pop(0)
			a = None
			b = None
			if x.left:
				a = x.left.data
				q.append(x.left)
			if x.right:
				b = x.right.data
				q.append(x.right)
			if a and b:
				l.append((gdc(max(a, b), min(a, b)), x.data))
		l.sort(reverse=True)
		if not l:
			return 0
		return l[0][1]


class Solution:

	def __init__(self):
		self.maxVal = 0
		self.node = 0

	def gcd(self, v1, v2):
		if v1 == 0 or v2 == 0:
			return -1
		a = max(v1, v2)
		b = min(v1, v2)
		if a % b == 0:
			return b
		else:
			while a != b:
				if a > b:
					a -= b
				elif b > a:
					b -= a
			return b

	def traverse(self, root):
		if root is None:
			return 0
		lv = self.traverse(root.left)
		rv = self.traverse(root.right)
		gcdval = self.gcd(lv, rv)
		if gcdval > self.maxVal:
			self.node = root.data
			self.maxVal = gcdval
		elif gcdval == self.maxVal:
			self.node = max(self.node, root.data)
		return root.data

	def maxGCD(self, root):
		self.traverse(root)
		return self.node


import math

def solve(node, d):
	if node is None:
		return None
	left = solve(node.left, d)
	right = solve(node.right, d)
	if left and right:
		gcd = math.gcd(left, right)
		if gcd > d['max_gcd']:
			d['max_gcd'] = gcd
			d['par_node'] = node.data
		if gcd == d['max_gcd']:
			d['par_node'] = max(d['par_node'], node.data)
	return node.data

class Solution:

	def maxGCD(self, root):
		d = {'max_gcd': 0, 'par_node': 0}
		solve(root, d)
		return d['par_node']


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)

def inorder(root):
	global mxGCD
	global ans
	if not root:
		return
	if root.left and root.right:
		temp = gcd(root.left.data, root.right.data)
		if mxGCD < temp:
			ans = root.data
			mxGCD = temp
		elif mxGCD == temp:
			ans = max(ans, root.data)
	inorder(root.left)
	inorder(root.right)
	return

class Solution:
	mxGCD = 0
	ans = 0

	def maxGCD(self, root):
		self.mxGCD = 0
		self.ans = 0
		self.getAns(root)
		return self.ans

	def getAns(self, root):
		if root == None:
			return
		self.getAns(root.left)
		self.getAns(root.right)
		if root.left != None and root.right != None:
			temp = gcd(root.left.data, root.right.data)
			if self.mxGCD < temp:
				self.ans = root.data
				self.mxGCD = temp
			elif self.mxGCD == temp and root.data > self.ans:
				self.ans = root.data


import math

class Solution:

	def maxGCD(self, root):
		ans = 0
		max_gcd = float('-inf')

		def solve(root):
			nonlocal ans, max_gcd
			if root is None:
				return 0
			if root.left and root.right:
				val = math.gcd(root.left.data, root.right.data)
				if val > max_gcd or (val == max_gcd and root.data > ans):
					max_gcd = val
					ans = root.data
			solve(root.left)
			solve(root.right)
		if root is None:
			return -1
		solve(root)
		return ans


class Solution:

	def maxGCD(self, root):

		def gcd(m, n):
			if m % n == 0:
				return n
			return gcd(n, m % n)
		D = {}

		def preorder(root, D):
			if root:
				if root.left and root.right:
					D[root] = gcd(max(root.left.data, root.right.data), min(root.left.data, root.right.data))
				preorder(root.left, D)
				preorder(root.right, D)
		preorder(root, D)
		ans = 0
		if D:
			y = max(D.values())
		keys = D.keys()
		for el in keys:
			if D[el] == y:
				ans = max(ans, el.data)
		return ans


class Solution:

	def gcd(self, a, b):
		if not a:
			return b
		else:
			return self.gcd(b % a, a)

	def maxGCD(self, root):
		self.ans = int()
		self.g = int()
		if not root:
			return 0

		def solve(root):
			if not root:
				return
			if root.left and root.right:
				cur_gcd = self.gcd(root.left.data, root.right.data)
				if cur_gcd > self.g:
					self.g = cur_gcd
					self.ans = root.data
				if cur_gcd == self.g:
					self.ans = max(self.ans, root.data)
			solve(root.left)
			solve(root.right)
		solve(root)
		return self.ans


class Solution:

	def GCD(self, a, b):
		if b == 0:
			return a
		if a == 0:
			return b
		if a == b:
			return b
		if a > b:
			return self.GCD(b, a % b)
		else:
			return self.GCD(a, b % a)

	def solver(self, root):
		global max_denom
		global mxd_node
		gcd = -1
		if not root:
			return -1
		l_gcd = self.solver(root.left)
		r_gcd = self.solver(root.right)
		if l_gcd != -1 and r_gcd != -1:
			gcd = self.GCD(l_gcd, r_gcd)
		else:
			gcd = -1
		if l_gcd != -1 and r_gcd != -1:
			if gcd > max_denom:
				max_denom = gcd
				mxd_node = root.data
		return root.data

	def maxGCD(self, root):
		global max_denom
		global mxd_node
		if not root:
			return 0
		max_denom = 0
		mxd_node = 0
		self.solver(root)
		return mxd_node


import math

class Solution:

	def __init__(self):
		self.ans = 0
		self.gc = 0

	def solve(self, root):
		if root == None:
			return 0
		if root.left and root.right:
			x = math.gcd(root.left.data, root.right.data)
			if x > self.gc:
				self.gc = x
				self.ans = root.data
			elif x == self.gc:
				self.ans = max(self.ans, root.data)
		if root.left:
			self.solve(root.left)
		if root.right:
			self.solve(root.right)

	def maxGCD(self, root):
		if root == None:
			return 0
		self.solve(root)
		return self.ans


import math

class Solution:

	def maxGCD(self, root):

		def gcdOfNode(node):
			if node.left is None:
				return -1
			if node.right is None:
				return -1
			a = node.left.data
			b = node.right.data
			return math.gcd(a, b)
		ans = 0
		maxGcd = 0

		def dfs(node):
			nonlocal ans, maxGcd
			if node is None:
				return
			curGcd = gcdOfNode(node)
			if maxGcd <= curGcd:
				ans = max(ans, node.data) if maxGcd == curGcd else node.data
				maxGcd = curGcd
			dfs(node.left)
			dfs(node.right)
		dfs(root)
		return ans


class Solution:

	def helper(self, root, ans):
		if not root:
			return 0
		if root.left and root.right:
			ma = max(root.left.data, root.right.data)
			mi = min(root.left.data, root.right.data)
			temp = self.gcd(mi, ma)
			if ans[1] < temp:
				ans[0] = root.data
				ans[1] = temp
			elif ans[1] == temp:
				if ans[0] < root.data:
					ans[0] = root.data
		self.helper(root.left, ans)
		self.helper(root.right, ans)
		return 0

	def gcd(self, a, b):
		if a == 0:
			return b
		return self.gcd(b % a, a)

	def maxGCD(self, root):
		ans = [0, 0]
		self.helper(root, ans)
		return ans[0]


class Solution:

	def gcd(self, a, b):
		if a == 0:
			return b
		return self.gcd(b % a, a)

	def maxGCD(self, root):
		self.res_gcd = 0
		self.nodeVal = 0
		q = deque([])
		q.append(root)
		while q:
			curr = q.popleft()
			if curr:
				if curr.left and curr.right:
					curr_gcd = self.gcd(curr.left.data, curr.right.data)
					if curr_gcd > self.res_gcd or (curr_gcd == self.res_gcd and self.nodeVal < curr.data):
						self.res_gcd = curr_gcd
						self.nodeVal = curr.data
				q.append(curr.left)
				q.append(curr.right)
		return self.nodeVal


import math

class Solution:

	def maxGCD(self, root):
		ans = 0
		mxGcd = 0
		(anss, ans) = self.Traverse(root, ans, mxGcd)
		return anss

	def Traverse(self, root, ans, mxGcd):
		if root.left and root.right:
			temp = math.gcd(root.left.data, root.right.data)
			if temp > mxGcd:
				mxGcd = temp
				ans = root.data
			if temp == mxGcd and ans < root.data:
				ans = root.data
			(temp, mxG1) = self.Traverse(root.left, ans, mxGcd)
			(temp1, mxG2) = self.Traverse(root.right, ans, mxGcd)
			if mxGcd < mxG1:
				mxGcd = mxG1
				ans = temp
			if mxGcd == mxG1 and ans < temp:
				ans = temp
			if mxGcd < mxG2:
				mxGcd = mxG2
				ans = temp1
			if mxGcd == mxG2 and ans < temp1:
				ans = temp1
		elif root.left:
			(temp, mxG1) = self.Traverse(root.left, ans, mxGcd)
			if mxGcd < mxG1:
				mxGcd = mxG1
				ans = temp
			if mxGcd == mxG1 and ans < temp:
				ans = temp
		elif root.right:
			(temp1, mxG2) = self.Traverse(root.right, ans, mxGcd)
			if mxGcd < mxG2:
				mxGcd = mxG2
				ans = temp1
			if mxGcd == mxG2 and ans < temp1:
				ans = temp1
		return (ans, mxGcd)


def GCDutil(a, b):
	if a == 0:
		return b
	return GCDutil(b % a, a)

def GCD(a, b):
	return GCDutil(min(a, b), max(a, b))

def maxGCDutil(root, ans, gcd):
	if root is None:
		return
	if root.left is None and root.right is None:
		return
	if root.left and root.right:
		x = GCD(root.left.data, root.right.data)
		if gcd[0] < x or (gcd[0] == x and root.data > ans[0]):
			gcd[0] = x
			ans[0] = root.data
	maxGCDutil(root.left, ans, gcd)
	maxGCDutil(root.right, ans, gcd)

class Solution:

	def maxGCD(self, root):
		if root is None:
			return -1
		ans = [0]
		gcd = [1]
		maxGCDutil(root, ans, gcd)
		return ans[0]


from collections import deque
from math import gcd

class Solution:

	def maxGCD(self, root):
		if not root:
			return 0
		if not root.left and root.right:
			return 0
		q = deque()
		q.append(root)
		res = root.data
		gd = -float('inf')
		while q:
			for i in range(len(q)):
				n = q.popleft()
				if n.left and n.right:
					cur = gcd(n.left.data, n.right.data)
					if cur > gd:
						res = n.data
						gd = cur
					elif cur == gd and n.data > res:
						res = n.data
						gd = cur
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
		return res


class Solution:

	def find_gcd(self, node) -> int:
		if node.left is None or node.right is None:
			return -1
		(lo, hi) = sorted([node.left.data, node.right.data])
		while hi % lo:
			(hi, lo) = (lo, hi - hi // lo * lo)
		return lo

	def maxGCD(self, root):
		(ans, gcd_hi) = (0, 1)
		if root is not None:
			stack = [root]
		while stack:
			for node in [stack[0].left, stack[0].right]:
				if node is not None:
					stack.append(node)
			a = self.find_gcd(stack[0])
			if a > gcd_hi or (a == gcd_hi and ans < stack[0].data):
				gcd_hi = a
				ans = stack[0].data
			root = stack.pop(0)
		return ans


from collections import defaultdict

class Solution:

	def find_gcd(self, node) -> int:
		if node.left is None or node.right is None:
			return -1
		(lo, hi) = sorted([node.left.data, node.right.data])
		while hi % lo:
			c = hi // lo
			(hi, lo) = (lo, hi - c * lo)
		return lo

	def maxGCD(self, root):
		gcd_hi = 1
		ans = 0
		if root is not None:
			stack = [root]
		while stack:
			root = stack.pop()
			a = self.find_gcd(root)
			if a > gcd_hi or (a == gcd_hi and ans < root.data):
				gcd_hi = a
				ans = root.data
			if root.left is not None:
				stack.append(root.left)
			if root.right is not None:
				stack.append(root.right)
		return ans


class Solution:

	def gcd(self, a, b):
		if a < b:
			(a, b) = (b, a)
		if a % b == 0:
			return b
		return self.gcd(b, a % b)

	def fun(self, root, mx, res):
		if root.left and root.right:
			tmp = self.gcd(root.left.data, root.right.data)
			if tmp > mx:
				mx = tmp
				res = root.data
			elif tmp == mx:
				res = max(res, root.data)
		if root.left:
			(mx, res) = self.fun(root.left, mx, res)
		if root.right:
			(mx, res) = self.fun(root.right, mx, res)
		return (mx, res)

	def maxGCD(self, root):
		return self.fun(root, 0, 0)[1]


import math

class Solution:

	def maxGCD(self, root):
		ans = 0
		ma = 0

		def rec(node):
			if node == None:
				return -1
			nonlocal ans, ma
			l = rec(node.left)
			r = rec(node.right)
			if l != -1 and r != -1 and (math.gcd(l, r) > ma):
				ma = math.gcd(l, r)
				ans = node.data
			return node.data
		rec(root)
		return ans


import math

class Solution:

	def traverse(self, root):
		if root is None:
			return
		if root.left is not None and root.right is not None:
			curr_gcd = math.gcd(root.left.data, root.right.data)
			if curr_gcd > self.mgcd:
				self.mgcd = curr_gcd
				self.mroot = root.data
			elif curr_gcd == self.mgcd:
				self.mroot = max(self.mroot, root.data)
		self.traverse(root.left)
		self.traverse(root.right)

	def maxGCD(self, root):
		self.mgcd = 0
		self.mroot = 0
		self.traverse(root)
		return self.mroot


import math

class Solution:
	temp = 0
	ans = 0

	def solve(self, root):
		if root == None:
			return
		left = root.left.data if root.left != None else 0
		right = root.right.data if root.right != None else 0
		gcd = 0
		if left != 0 and right != 0:
			gcd = math.gcd(left, right)
			if gcd > self.temp:
				self.temp = gcd
				self.ans = root.data
			elif gcd == self.temp:
				self.ans = max(self.ans, root.data)
		self.solve(root.left)
		self.solve(root.right)

	def maxGCD(self, root):
		if root == None:
			return 0
		self.solve(root)
		return self.ans


import math

class Solution:

	def maxGCD(self, root):
		if root.left == None and root.right == None:
			return 0

		def dfs(node):
			if node == None:
				return
			if node.left and node.right:
				res.append([math.gcd(node.left.data, node.right.data), node.data])
			dfs(node.left)
			dfs(node.right)
		res = []
		dfs(root)
		gl = [res[j][0] for j in range(len(res))]
		res = sorted(res, key=lambda x: (x[0], x[1]))
		if res == []:
			return 0
		return res[-1][1]


class Solution:

	def gcd(self, a, b):
		if a == 0:
			return b
		return self.gcd(b % a, a)

	def traverse(self, root):
		if root.left and root.right:
			val = self.gcd(root.left.data, root.right.data)
			if val > self.max_gcd:
				self.max_gcd = val
				self.max_node = root.data
			elif val == self.max_gcd and root.data > self.max_node:
				self.max_node = root.data
		if root.left:
			self.traverse(root.left)
		if root.right:
			self.traverse(root.right)

	def maxGCD(self, root):
		if not root:
			return 0
		self.max_gcd = 0
		self.max_node = 0
		self.traverse(root)
		return self.max_node


import math

class Solution:

	def maxGCD(self, root):
		if not root:
			return 0
		(maxgcd, maxv) = (0, 0)
		(stack, ans) = ([root], [])
		while stack:
			root = stack.pop()
			(right, left) = (0, 0)
			if root.right:
				stack.append(root.right)
				right = root.right.data
			if root.left:
				stack.append(root.left)
				left = root.left.data
			gcdv = 0
			if right != 0 and left != 0:
				gcdv = math.gcd(right, left)
			if gcdv > maxgcd:
				maxgcd = gcdv
				maxv = root.data
			elif gcdv == maxgcd:
				maxv = max(maxv, root.data)
		if maxgcd != 0:
			return maxv
		return 0


from math import gcd

class Solution:

	def maxGCD(self, root):
		return self.gcd(root)[1]

	def gcd(self, node):
		if node is None:
			return (0, 0)
		a = (0, 0)
		if node.left and node.right:
			a = (gcd(node.left.data, node.right.data), node.data)
		b = self.gcd(node.left)
		c = self.gcd(node.right)
		return max(a, b, c)


from collections import deque

class Solution:

	def gcd(self, a, b):
		if b == 0:
			return abs(a)
		else:
			return self.gcd(b, a % b)

	def maxGCD(self, root):
		if root == None:
			return 0
		(maxGcd, ans) = (0, 0)
		q = deque()
		q.append(root)
		while len(q) > 0:
			sz = len(q)
			while sz:
				curr = q[0]
				q.popleft()
				if curr.left and curr.right:
					newGcd = self.gcd(curr.left.data, curr.right.data)
					if newGcd > maxGcd:
						maxGcd = newGcd
						ans = curr.data
					elif newGcd == maxGcd:
						ans = max(ans, curr.data)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
				sz -= 1
		return ans


class Solution:

	def __init__(self):
		self.max_gcd = 0
		self.val = 0

	def gcd(self, a, b):
		if b == 0:
			return a
		else:
			return self.gcd(b, a % b)

	def maxGCD(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 0
		elif root.left and root.right:
			hcf = self.gcd(root.left.data, root.right.data)
			if hcf > self.max_gcd:
				self.max_gcd = hcf
				self.val = root.data
			elif hcf == self.max_gcd:
				self.val = max(self.val, root.data)
		self.maxGCD(root.left)
		self.maxGCD(root.right)
		return self.val


import math

class Solution:

	def maxGCD(self, root):
		maxgcd = 0
		res = 0

		def dfs(root):
			nonlocal maxgcd, res
			gcd_ = 0
			left = dfs(root.left) if root.left else 0
			right = dfs(root.right) if root.right else 0
			if left != 0 and right != 0:
				gcd_ = math.gcd(left, right)
			if gcd_ and gcd_ > maxgcd:
				res = root.data
				maxgcd = gcd_
			return root.data
		dfs(root)
		return res


class Solution:

	def maxGCD(self, root):

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)

		def recur(root):
			nonlocal res, max_gcd
			if root:
				recur(root.left)
				recur(root.right)
				if root.left and root.right:
					cur = gcd(root.left.data, root.right.data)
					if cur > max_gcd:
						res = root.data
						max_gcd = cur
					elif cur == max_gcd:
						res = max(res, root.data)
		res = max_gcd = 0
		try:
			recur(root)
		except Exception as e:
			print(e)
		return res


class Solution:

	def maxGCD(self, root):
		if root == None:
			return 0
		maxgcd = 0
		maxgcd_node = 0
		q = [root]
		while q:
			nq = []
			for i in q:
				if i.left:
					nq.append(i.left)
				if i.right:
					nq.append(i.right)
				if i.left and i.right:
					gcd = GCD(i.left.data, i.right.data)
					if gcd > maxgcd:
						maxgcd = gcd
						maxgcd_node = i.data
					elif gcd == maxgcd:
						if i.data > maxgcd_node:
							maxgcd_node = i.data
			q = nq
		return maxgcd_node

def GCD(num1, num2):
	if num2 > num1:
		(num1, num2) = (num2, num1)
	if num1 == 0:
		return num2
	if num2 == 0:
		return num1
	while num2 != 0:
		remainder = num1 % num2
		if remainder == 0:
			return num2
		num1 = num2
		num2 = remainder


import math

class Solution:

	def maxGCD(self, root):
		ans = 0
		node = 0

		def fun(root):
			nonlocal ans, node
			if not root:
				return
			fun(root.left)
			fun(root.right)
			if root.left and root.right:
				a = root.left.data
				b = root.right.data
				g = math.gcd(a, b)
				if g > ans:
					ans = g
					node = root.data
				elif g == ans and root.data > node:
					node = root.data
		fun(root)
		return node


class Solution:

	def __init__(self):
		self.ans = 0
		self.ma = 0

	def GCD(self, a, b):
		if a == 0 or b == 0:
			return a if b == 0 else b
		if a > b:
			return self.GCD(b, a % b)
		return self.GCD(a, b % a)

	def maxGCD(self, root):
		if root == None:
			return self.ans
		self.maxGCD(root.left)
		left = root.left
		right = root.right
		if left != None and right != None:
			temp = self.GCD(left.data, right.data)
			if temp > self.ma:
				self.ma = temp
				self.ans = root.data
		self.maxGCD(root.right)
		return self.ans


import math

class Solution:

	def maxGCD(self, root):
		ans = 0
		mx = 0

		def solve(root):
			nonlocal ans, mx
			if not root:
				return
			if root.left and root.right:
				gcd = math.gcd(root.left.data, root.right.data)
				if gcd >= mx:
					ans = root.data if gcd > mx else max(root.data, ans)
					mx = gcd
			solve(root.left)
			solve(root.right)
		solve(root)
		return ans


class Solution:

	def __init__(self):
		(self.max_gcd, self.res) = (-float('inf'), 0)

	def maxGCD(self, root):
		self.dfs(root)
		return self.res

	def dfs(self, root):
		if root.left and root.right:
			temp = self.gcd(root.left.data, root.right.data)
			if self.max_gcd < temp:
				self.res = root.data
				self.max_gcd = temp
			elif self.max_gcd == temp:
				self.res = max(self.res, root.data)
		if root.left:
			self.dfs(root.left)
		if root.right:
			self.dfs(root.right)

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)


from collections import deque

class Solution:

	def maxGCD(self, root):
		ans_max = 0
		gc = float('-inf')
		q = deque()
		q.append(root)
		while q:
			node = q.popleft()
			if node.left and node.right:
				d = node.data
				l = node.left.data
				r = node.right.data
				gc1 = self.gcd(l, r)
				if gc1 >= gc:
					ans_max = d
					gc = gc1
				q.append(node.left)
				q.append(node.right)
			elif node.left:
				q.append(node.left)
			elif node.right:
				q.append(node.right)
		return ans_max

	def gcd(self, a, b):
		if a % b == 0:
			return b
		return self.gcd(b, a % b)


import math

class Solution:

	def maxGCD(self, root):
		if root.left == None and root.right == None:
			return 0

		def helper(root):
			nonlocal ans
			nonlocal maxgcd
			if root == None:
				return
			helper(root.left)
			helper(root.right)
			if root.left != None and root.right != None:
				if math.gcd(root.left.data, root.right.data) > maxgcd or (math.gcd(root.left.data, root.right.data) == maxgcd and ans < root.data):
					maxgcd = math.gcd(root.left.data, root.right.data)
					ans = root.data
			return
		ans = 0
		maxgcd = 1
		helper(root)
		return ans


import math

class Solution:

	def __init__(self):
		self.max_gcd_root = 0
		self.max_gcd = 0

	def solve(self, root):
		if root is None:
			return -1
		if root.left is not None and root.right is not None:
			gcd = math.gcd(root.left.data, root.right.data)
			if gcd > self.max_gcd:
				self.max_gcd_root = root.data
				self.max_gcd = gcd
			elif gcd == self.max_gcd:
				self.max_gcd_root = max(self.max_gcd_root, root.data)
		self.solve(root.left)
		self.solve(root.right)

	def maxGCD(self, root):
		self.solve(root)
		return self.max_gcd_root


class Solution:

	def gcd(self, val1, val2):
		if val1 == 0:
			return val2
		if val2 == 0:
			return val1
		smaller_val = min(val1, val2)
		larger_val = max(val1, val2)
		return self.gcd(smaller_val, larger_val % smaller_val)

	def maxGcdHelper(self, node):
		if node:
			if node.left and node.right:
				sibling_gcd = self.gcd(node.left.data, node.right.data)
				if sibling_gcd > self.ans:
					self.ans = sibling_gcd
					self.parent = node.data
				elif sibling_gcd == self.ans:
					self.parent = max(self.parent, node.data)
			self.maxGcdHelper(node.left)
			self.maxGcdHelper(node.right)

	def maxGCD(self, root):
		self.ans = 0
		self.parent = None
		self.maxGcdHelper(root)
		return self.parent or 0