Given a BST (Binary Search Tree), find the shortest range [x, y], such that, at least one node of every level of the BST lies in the range.
If there are multiple ranges with the same gap (i.e. (y-x)) return the range with the smallest x.
Example 1:
Input:
              8
          /   \
         3     10
       /  \      \
      2    6      14
          / \     /
         4   7   12
                /  \
               11   13
Output: 6 11
Explanation: Level order traversal of the tree 
is [8], [3, 10], [2, 6, 14], [4, 7, 12], [11, 13]. 
The shortest range which satisfies the above 
mentioned condition is [6, 11]. 
Example 2:
Input:
   12
    \
     13
       \
        14
         \
          15
           \
           16
Output: 12 16
Explanation: Each level contains one node, 
so the shortest range is [12, 16].
Your Task:
You don't need to read input or print anything. Complete the function shortestRange() which takes the root of the tree as an input parameter and returns the pair of numbers
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Node Value ≤ 10^{5}

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Amortized analysis

Range queries
Skill types: Amortized analysis

Data structures

Range queries
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def shortestRange(self, root):

        # Return pair/tuple of range

        # Your code goes here

Solutions:
from heapq import heappop, heappush

def findRange(lists):
	if not lists:
		return (-1, -1)
	high = -99999
	p = (0, 99999)
	q = []
	for i in range(len(lists)):
		if not lists[i]:
			return (-1, -1)
		heappush(q, (lists[i][0], i, 0))
		high = max(high, lists[i][0])
	while True:
		top = heappop(q)
		low = top[0]
		i = top[1]
		j = top[2]
		if high - low < p[1] - p[0]:
			p = (low, high)
		if j == len(lists[i]) - 1:
			return p
		heappush(q, (lists[i][j + 1], i, j + 1))
		high = max(high, lists[i][j + 1])
from collections import deque

def levelorder(root):
	if root == None:
		return (-1, -1)
	q = deque([])
	q.append(root)
	ans = []
	while len(q) > 0:
		n = len(q)
		st = []
		for i in range(1, n + 1):
			temp = q.popleft()
			st.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		ans.append(st)
	return ans

class Solution:

	def shortestRange(self, root):
		ans = levelorder(root)
		return findRange(ans)


def inorder_(root, inArr, lvlSet, lvl):
	if root == None:
		return
	inorder_(root.left, inArr, lvlSet, lvl + 1)
	inArr.append([root.data, lvl])
	lvlSet.add(lvl)
	inorder_(root.right, inArr, lvlSet, lvl + 1)

def thisIsAns(freq, levels):
	for i in range(levels):
		if freq[i] > 0:
			continue
		return False
	return True

def findMinRange(root):
	inArr = []
	lvlSet = set()
	inorder_(root, inArr, lvlSet, 1)
	n = len(inArr)
	if n == 1:
		return [root.data, root.data]
	levels = len(lvlSet)
	i = 0
	j = i
	ans = None
	min = 0
	freq = [0] * levels
	flg = True
	while i <= j and j < n:
		if flg:
			freq[inArr[j][1] - 1] += 1
		if thisIsAns(freq, levels):
			p_ans = [inArr[i][0], inArr[j][0]]
			p_min = p_ans[1] - p_ans[0]
			if ans is None:
				ans = p_ans
				min = p_min
			elif p_min < min:
				ans = p_ans
				min = p_min
			elif p_min == min and p_ans[0] < ans[0]:
				ans = p_ans
			freq[inArr[i][1] - 1] -= 1
			i += 1
			flg = False
			continue
		flg = True
		j += 1
	return ans

class Solution:

	def shortestRange(self, root):
		return findMinRange(root)


from heapq import heappush, heappop
from collections import deque

class Solution:

	def level_order(self, root):
		q = deque()
		trav = [[root.data]]
		if root.left:
			q.append(root.left)
		if root.right:
			q.append(root.right)
		while q:
			n = len(q)
			tem = []
			for i in range(n):
				nod = q.popleft()
				tem.append(nod.data)
				if nod.left:
					q.append(nod.left)
				if nod.right:
					q.append(nod.right)
			if tem[0] > root.data:
				trav.append([tem[0]])
			elif tem[-1] < root.data:
				trav.append([tem[-1]])
			else:
				for i in range(n):
					if tem[i] > root.data:
						trav.append([tem[i - 1], tem[i]])
						break
		return trav

	def shortestRange(self, root):
		if root.left is None and root.right is None:
			return [root.data, root.data]
		node = self.level_order(root)
		n = len(node)
		heap = []
		maxi = -999999
		for i in range(n):
			heappush(heap, (node[i][0], i, 0))
			maxi = max(maxi, node[i][0])
		leng = maxi - heap[0][0]
		st = heap[0][0]
		en = maxi
		while heap:
			(nod, ro, co) = heappop(heap)
			if len(node[ro]) == co + 1:
				break
			heappush(heap, (node[ro][co + 1], ro, co + 1))
			maxi = max(maxi, node[ro][co + 1])
			if maxi - heap[0][0] < leng:
				leng = maxi - heap[0][0]
				st = heap[0][0]
				en = maxi
			elif maxi - heap[0][0] == leng and st > heap[0][0]:
				st = heap[0][0]
				en = maxi
		return [st, en]


from heapq import *
from collections import defaultdict

class Solution:

	def shortestRange(self, root):

		def traverse(node, level, arr):
			if not node:
				return
			arr[level] += [node.data]
			traverse(node.left, level + 1, arr)
			traverse(node.right, level + 1, arr)
		arr = defaultdict(list)
		traverse(root, 0, arr)
		h = []
		n = len(arr)
		heapify(h)
		maxm = -10 ** 9
		for i in range(n):
			heappush(h, [arr[i][0], i, 0])
			maxm = max(maxm, arr[i][0])
		ans = 10 ** 9
		right = 10 ** 9
		while h:
			(ele, level, ind) = heappop(h)
			if ans > maxm - ele:
				ans = maxm - ele
				right = maxm
			if len(arr[level]) == ind + 1:
				break
			maxm = max(maxm, arr[level][ind + 1])
			heappush(h, [arr[level][ind + 1], level, ind + 1])
		return [right - ans, right]


def inorder_(root, inArr, lvlSet, lvl):
	if root == None:
		return
	inorder_(root.left, inArr, lvlSet, lvl + 1)
	inArr.append([root.data, lvl])
	lvlSet.add(lvl)
	inorder_(root.right, inArr, lvlSet, lvl + 1)

def thisIsAns(freq, levels):
	for i in range(levels):
		if freq[i] > 0:
			continue
		return False
	return True

def findMinRange(root):
	inArr = []
	lvlSet = set()
	inorder_(root, inArr, lvlSet, 1)
	n = len(inArr)
	if n == 1:
		return [root.data, root.data]
	levels = len(lvlSet)
	i = 0
	j = i
	ans = None
	min = 0
	freq = [0] * levels
	flg = True
	while i <= j and j < n:
		if flg:
			freq[inArr[j][1] - 1] += 1
		if thisIsAns(freq, levels):
			p_ans = [inArr[i][0], inArr[j][0]]
			p_min = p_ans[1] - p_ans[0]
			if ans is None:
				ans = p_ans
				min = p_min
			elif p_min < min:
				ans = p_ans
				min = p_min
			elif p_min == min and p_ans[0] < ans[0]:
				ans = p_ans
			freq[inArr[i][1] - 1] -= 1
			i += 1
			flg = False
			continue
		flg = True
		j += 1
	return ans

class Solution:

	def shortestRange(self, root):
		return findMinRange(root)

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	from collections import deque
	t = int(input())
	for _ in range(t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		ans = obj.shortestRange(root)
		print(ans[0], ans[1])


from heapq import heappop, heappush

def findRange(lists):
	if not lists:
		return (-1, -1)
	high = -99999
	p = (0, 99999)
	q = []
	for i in range(len(lists)):
		if not lists[i]:
			return (-1, -1)
		heappush(q, (lists[i][0], i, 0))
		high = max(high, lists[i][0])
	while True:
		top = heappop(q)
		low = top[0]
		i = top[1]
		j = top[2]
		if high - low < p[1] - p[0]:
			p = (low, high)
		if j == len(lists[i]) - 1:
			return p
		heappush(q, (lists[i][j + 1], i, j + 1))
		high = max(high, lists[i][j + 1])
from collections import deque

def levelorder(root):
	if root == None:
		return (-1, -1)
	q = deque([])
	q.append(root)
	ans = []
	while len(q) > 0:
		n = len(q)
		st = []
		for i in range(1, n + 1):
			temp = q.popleft()
			st.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		ans.append(st)
	return ans

class Solution:

	def shortestRange(self, root):
		ans = levelorder(root)
		return findRange(ans)

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	from collections import deque
	t = int(input())
	for _ in range(t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		ans = obj.shortestRange(root)
		print(ans[0], ans[1])


from collections import defaultdict
import heapq

class Solution:

	def level_order(self, root, dic, level):
		if root == None:
			return
		dic[level].append(root.data)
		self.level_order(root.left, dic, level + 1)
		self.level_order(root.right, dic, level + 1)

	def shortestRange(self, root):
		dic = defaultdict(list)
		self.level_order(root, dic, 0)
		heap = []
		(mn, mx) = (float('inf'), 0)
		for i in range(len(dic)):
			heapq.heappush(heap, [dic[i][0], i, 1])
			mn = min(mn, dic[i][0])
			mx = max(mx, dic[i][0])
			dic[i].append(float('inf'))
		ans = [mn, mx]
		while heap:
			h = heapq.heappop(heap)
			heapq.heappush(heap, [dic[h[1]][h[2]], h[1], h[2] + 1])
			mx = max(mx, dic[h[1]][h[2]])
			if ans[1] - ans[0] > mx - heap[0][0]:
				ans = [heap[0][0], mx]
				if ans[1] - ans[0] == 0:
					return ans
			if mx == float('inf'):
				return ans
		return ans

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	from collections import deque
	t = int(input())
	for _ in range(t):
		s = input()
		root = buildTree(s)
		obj = Solution()
		ans = obj.shortestRange(root)
		print(ans[0], ans[1])


from heapq import heapify, heappush, heappop

class Solution:

	def shortestRange(self, root):
		l = []
		q = [root]
		t = [root.data]
		while q:
			q1 = []
			t1 = []
			l.append(t[:])
			for i in q:
				if i.left:
					q1.append(i.left)
					t1.append(i.left.data)
				if i.right:
					q1.append(i.right)
					t1.append(i.right.data)
			q = q1
			t = t1
		h = []
		heapify(h)
		mn = float('inf')
		mx = -float('inf')
		for i in range(len(l)):
			mn = min(mn, l[i][0])
			mx = max(mx, l[i][0])
			heappush(h, (l[i][0], i, 0))
		s = mn
		e = mx
		ans = e - s
		a = mn
		b = mx
		while h:
			(v, i, j) = heappop(h)
			if j == len(l[i]) - 1:
				return [s, e]
			heappush(h, (l[i][j + 1], i, j + 1))
			a = h[0][0]
			b = max(b, l[i][j + 1])
			if b - a < ans:
				ans = b - a
				s = a
				e = b
			elif b - a == ans:
				if s > a:
					s = a
					e = b
		return [s, e]


from heapq import heappop, heappush

class Solution:

	def shortestRange(self, root):
		ans = []
		q = []
		q.append(root)
		while q:
			n = len(q)
			st = []
			for i in range(0, n):
				temp = q.pop(0)
				st.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			ans.append(st)
		high = -99999
		p = (0, 99999)
		pq = []
		for i in range(len(ans)):
			if not ans[i]:
				return (-1, -1)
			heappush(pq, (ans[i][0], i, 0))
			high = max(high, ans[i][0])
		while True:
			top = heappop(pq)
			low = top[0]
			i = top[1]
			j = top[2]
			if high - low < p[1] - p[0]:
				p = (low, high)
			if j == len(ans[i]) - 1:
				return p
			heappush(pq, (ans[i][j + 1], i, j + 1))
			high = max(high, ans[i][j + 1])


class Solution:

	def shortestRange(self, root):
		lists = get_lists(root)
		min_range = (min((l[0] for l in lists)), max((l[0] for l in lists)))
		indexes = [0 for _ in range(len(lists))]
		while True:
			nums = [l[i] for (l, i) in zip(lists, indexes)]
			(mx, mn) = (max(nums), min(nums))
			if mx - mn < min_range[1] - min_range[0]:
				min_range = (mn, mx)
			min_i = 0
			min_v = nums[0]
			for (i, v) in enumerate(nums):
				if v < min_v:
					min_v = v
					min_i = i
			if len(lists[min_i]) == indexes[min_i] + 1:
				return min_range
			indexes[min_i] += 1

def get_lists(root):
	(queue, next_layer, res) = ([root], [], [])
	while queue:
		res.append([])
		for node in queue:
			res[-1].append(node.data)
			if node.left:
				next_layer.append(node.left)
			if node.right:
				next_layer.append(node.right)
		(queue, next_layer) = (next_layer, [])
	return res


import heapq
from heapq import heapify, heappop, heappush

class Solution:

	def shortestRange(self, root):
		vec = []
		q = []
		q.append(root)
		while q:
			sze = len(q)
			tmp = []
			while sze > 0:
				node = q.pop(0)
				if node is not None:
					tmp.append(node.data)
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
				sze -= 1
			vec.append(tmp)
		h = []
		Max = -100000000000.0
		for i in range(len(vec)):
			h.append([vec[i][0], i, 0])
			Max = max(Max, vec[i][0])
		heapify(h)
		Diff = Max - h[0][0]
		Range = [Max, h[0][0]]
		while True:
			(Min, r, c) = heappop(h)
			if Max - Min < Diff:
				Diff = Max - Min
				Range = [Min, Max]
			if c + 1 >= len(vec[r]):
				break
			num = vec[r][c + 1]
			Max = max(Max, num)
			heappush(h, [num, r, c + 1])
		Range.sort()
		return Range
		print(vec)
		return vec


from collections import deque
import heapq

class Solution:

	def shortestRange(self, root):
		l = []

		def levelorder(root):
			q = deque([root])
			while q:
				size = len(q)
				temp = []
				while size:
					node = q.popleft()
					temp.append(node.data)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
					size -= 1
				l.append(temp)
		levelorder(root)
		h = []
		heapq.heapify(h)
		n = len(l)
		(min_, max_) = (float('inf'), float('-inf'))
		for level in range(n):
			value = l[level][0]
			heapq.heappush(h, (value, level, 0))
			min_ = min(value, min_)
			max_ = max(value, max_)
		(a, b) = (min_, max_)
		while True:
			(c_value, c_level, c_index) = heapq.heappop(h)
			if max_ - c_value < b - a:
				a = c_value
				b = max_
			if len(l[c_level]) == c_index + 1:
				break
			else:
				heapq.heappush(h, (l[c_level][c_index + 1], c_level, c_index + 1))
				max_ = max(max_, l[c_level][c_index + 1])
		return (a, b)


class Solution:

	def shortestRange(self, root):

class Solution:

	def storein(self, root, lvl, lin, llv):
		if not root:
			return
		self.storein(root.left, lvl + 1, lin, llv)
		lin.append(root.data)
		llv.append(lvl)
		self.storein(root.right, lvl + 1, lin, llv)

	def shortestRange(self, root):
		inorder = []
		level = []
		self.storein(root, 0, inorder, level)
		i = j = k = cntzero = 0
		maxDepth = max(level) + 1
		depth = [0] * maxDepth
		for k in range(len(level)):
			depth[level[k]] += 1
			if level[k] == 0:
				j = k
				break
		cntzero = depth.count(0)
		(x, y) = (inorder[0], inorder[-1])
		if cntzero == 0:
			(x, y) = (inorder[i], inorder[j])
		while i <= k and j < len(inorder):
			while j < len(inorder):
				if cntzero == 0:
					if y - x > inorder[j] - inorder[i]:
						(x, y) = (inorder[i], inorder[j])
					break
				j += 1
				if j >= len(inorder):
					break
				if depth[level[j]] == 0:
					cntzero -= 1
				depth[level[j]] += 1
			while not cntzero and i <= k:
				if y - x > inorder[j] - inorder[i]:
					(x, y) = (inorder[i], inorder[j])
				depth[level[i]] -= 1
				if depth[level[i]] == 0:
					cntzero += 1
				i += 1
		return (x, y)


from collections import defaultdict

class Solution:

	def shortestRange(self, root):
		global nums
		nums = []

		def getLevelOrder(root):
			global nums
			q = [root]
			while q:
				c = len(q)
				nums.append([node.data for node in q])
				while c:
					node = q.pop(0)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
					c -= 1
		getLevelOrder(root)
		n = len(nums)
		m = []
		for k in range(n):
			for num in nums[k]:
				m.append((num, k))
		m = sorted(m)
		d = 0
		(left, right) = (0, 0)
		freq = defaultdict(lambda : 0)
		mn = float('inf')
		(a, b) = (None, None)
		while right < len(m):
			if freq[m[right][1]] == 0:
				d += 1
			freq[m[right][1]] += 1
			if d == n:
				break
			right += 1
		if m[right][0] - m[left][0] < mn:
			(a, b) = (m[left][0], m[right][0])
			mn = m[right][0] - m[left][0]
		while right < len(m):
			while left < right:
				if freq[m[left][1]] > 1:
					freq[m[left][1]] -= 1
					left += 1
					if m[right][0] - m[left][0] < mn:
						(a, b) = (m[left][0], m[right][0])
						mn = m[right][0] - m[left][0]
				else:
					break
			freq[m[left][1]] -= 1
			left += 1
			right += 1
			d -= 1
			while right < len(m):
				if freq[m[right][1]] == 0:
					d += 1
				freq[m[right][1]] += 1
				if d == n:
					break
				right += 1
			if d == n and m[right][0] - m[left][0] < mn:
				(a, b) = (m[left][0], m[right][0])
				mn = m[right][0] - m[left][0]
		return [a, b]


import heapq
from collections import deque

class Solution:

	def shortestRange(self, root):
		numbers = []
		q = deque()
		q.append(root)
		while q:
			size = len(q)
			num = []
			while size:
				ele = q.popleft()
				num.append(ele.data)
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
				size -= 1
			numbers.append(num)

		def getrange(numbers):
			ans = [-10000000, 10000000]
			heap = []
			maxi = -999999999
			k = len(numbers)
			for i in range(k):
				mol = numbers[i][0]
				maxi = max(maxi, mol)
				heapq.heappush(heap, [mol, 0, i])
			while True:
				mini = heapq.heappop(heap)
				if ans[1] - ans[0] > maxi - mini[0]:
					ans[0] = mini[0]
					ans[1] = maxi
				mini[1] += 1
				cl = numbers[mini[2]]
				if mini[1] == len(cl):
					break
				else:
					mini[0] = cl[mini[1]]
					maxi = max(maxi, cl[mini[1]])
					heapq.heappush(heap, mini)
			return ans
		sol = getrange(numbers)
		return sol


class Solution:

	def shortestRange(self, root):
		import heapq
		map_ = {}
		queue = []
		queue.append((root, 0))
		while queue:
			(node, level) = queue.pop(0)
			if map_.get(level):
				map_[level].append(node.data)
			else:
				map_[level] = [node.data]
			if node.left:
				queue.append((node.left, level + 1))
			if node.right:
				queue.append((node.right, level + 1))
		nums = list(map_.values())
		pq = [(num[0], i, 0) for (i, num) in enumerate(nums)]
		heapq.heapify(pq)
		(left, right) = (float('-inf'), float('inf'))
		curmax = max([num[0] for num in nums])
		while pq:
			(curmin, arrayIndex, index) = heapq.heappop(pq)
			if right - left > curmax - curmin:
				(right, left) = (curmax, curmin)
			if index + 1 == len(nums[arrayIndex]):
				return [left, right]
			curmax = max(curmax, nums[arrayIndex][index + 1])
			heapq.heappush(pq, (nums[arrayIndex][index + 1], arrayIndex, index + 1))


import heapq

class Solution:

	def shortestRange(self, root):
		q = [root]
		temp = 1
		lvl = 0
		trav = []
		while q != []:
			ele = q.pop(0)
			trav.append([])
			trav[lvl].append(ele.data)
			temp -= 1
			if ele.left:
				q.append(ele.left)
			if ele.right:
				q.append(ele.right)
			if temp == 0:
				temp = len(q)
				lvl += 1
		trav = [i for i in trav if i != []]
		pq = []
		n = len(trav)
		maxx = 0
		for i in range(n):
			heapq.heappush(pq, (trav[i][0], i, 0))
			maxx = max(maxx, trav[i][0])
		ans = [pq[0][0], maxx]
		while True:
			(_, list_index, num_index) = heapq.heappop(pq)
			if num_index == len(trav[list_index]) - 1:
				break
			next_num = trav[list_index][num_index + 1]
			maxx = max(maxx, next_num)
			heapq.heappush(pq, (next_num, list_index, num_index + 1))
			if maxx - pq[0][0] < ans[1] - ans[0]:
				ans = [pq[0][0], maxx]
		return ans


class Solution:

	def level_order(self, root):
		res = []
		trav = [(root, 0)]
		while trav:
			(cur, depth) = trav.pop()
			if cur.right:
				trav.append((cur.right, depth + 1))
			if cur.left:
				trav.append((cur.left, depth + 1))
			if depth > len(res) - 1:
				res.append([cur.data])
			else:
				res[depth].append(cur.data)
		return res

	def shortestRange(self, root):
		KSortedArray = self.level_order(root)
		k = len(KSortedArray)
		arr = []
		for i in range(len(KSortedArray)):
			for j in KSortedArray[i]:
				arr.append((j, i))
		arr.sort()
		j = 0
		counts = {}
		total = 0
		ans = ()
		diff = 10000000.0
		for i in range(len(arr)):
			if arr[i][1] not in counts:
				total += 1
				counts[arr[i][1]] = 1
			else:
				counts[arr[i][1]] += 1
			if total == k:
				while total == k:
					if counts[arr[j][1]] > 1:
						counts[arr[j][1]] -= 1
						j += 1
					else:
						break
				if arr[i][0] - arr[j][0] < diff:
					ans = (arr[j][0], arr[i][0])
					diff = arr[i][0] - arr[j][0]
		return ans


import heapq

class Solution:

	def shortestRange(self, root):
		l = []
		q = [root]
		ll = []
		while q:
			for i in range(len(q)):
				x = q.pop(0)
				ll.append(x.data)
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)
			l.append(ll)
			ll = []
		h = []
		m = -1000000000
		for i in range(len(l)):
			heapq.heappush(h, (l[i][0], 0, i))
			m = max(m, l[i][0])
		min_r = m - h[0][0]
		maxi = m
		mini = h[0][0]
		while True:
			(a, b, c) = (h[0][0], h[0][1], h[0][2])
			if len(l[c]) - 1 == b:
				break
			heapq.heappop(h)
			heapq.heappush(h, (l[c][b + 1], b + 1, c))
			m = max(m, l[c][b + 1])
			if m - h[0][0] < min_r:
				maxi = m
				mini = h[0][0]
				min_r = m - h[0][0]
		return [mini, maxi]


class Solution:

	def storeValues(self, root, level, inorder):
		if not root:
			return
		inorder.append((root.data, level))
		self.storeValues(root.left, level + 1, inorder)
		self.storeValues(root.right, level + 1, inorder)

	def shortestRange(self, root):
		inorder = []
		self.storeValues(root, 0, inorder)
		inorder.sort()
		(a, b) = (max((i for (_, i) in inorder)) + 1, {})
		(m, n) = (inorder[0][0], inorder[-1][0])
		i = j = 0
		for (j, (_, t)) in enumerate(inorder):
			b[t] = b.get(t, 0) + 1
			while i < j and len(b) == a:
				if inorder[j][0] - inorder[i][0] < n - m:
					(m, n) = (inorder[i][0], inorder[j][0])
				if b[inorder[i][1]] == 1:
					del b[inorder[i][1]]
				else:
					b[inorder[i][1]] -= 1
				i += 1
		return [m, n]


from heapq import heappush, heappop
from collections import deque, defaultdict
from math import inf

class Solution:

	def level_order_traversal(self, root):
		Q = deque([root])
		traversal = defaultdict(list)
		level = 0
		traversal[level].append(root.data)
		while Q:
			level += 1
			size = len(Q)
			while size:
				node = Q.pop()
				if node.left:
					traversal[level].append(node.left.data)
					Q.appendleft(node.left)
				if node.right:
					traversal[level].append(node.right.data)
					Q.appendleft(node.right)
				size -= 1
		return traversal

	def shortestRange(self, root):
		traversal = self.level_order_traversal(root)
		heap = []
		k = len(traversal)
		max_val = 0
		for i in range(k):
			heappush(heap, (traversal[i][0], i, 1))
			max_val = max(max_val, traversal[i][0])
		(start, end) = (-inf, inf)
		while heap:
			cur_end = max_val
			if len(heap) == k:
				cur_start = heap[0][0]
			if cur_end - cur_start < end - start:
				(end, start) = (cur_end, cur_start)
			(_, i, j) = heappop(heap)
			if j != len(traversal[i]):
				heappush(heap, (traversal[i][j], i, j + 1))
				max_val = max(max_val, traversal[i][j])
		return (start, end)


from collections import defaultdict

class Solution:

	def dfs(self, root, level):
		global t
		temp = []
		t = max(t, level)
		if root.left:
			temp = self.dfs(root.left, level + 1)
		temp.append([root.data, level])
		if root.right:
			temp.extend(self.dfs(root.right, level + 1))
		return temp

	def shortestRange(self, root):
		global t
		t = 0
		l = self.dfs(root, 1)
		(cnt, j) = (0, 0)
		d = defaultdict(int)
		(x, y) = (0, float('inf'))
		for i in range(len(l)):
			d[l[i][1]] = d[l[i][1]] + 1
			if d[l[i][1]] == 1:
				cnt = cnt + 1
			while cnt == t:
				if y - x > l[i][0] - l[j][0]:
					(x, y) = (l[j][0], l[i][0])
				d[l[j][1]] = d[l[j][1]] - 1
				if d[l[j][1]] == 0:
					cnt = cnt - 1
				j = j + 1
		return (x, y)


class Solution:

	def inorder(self, node, level, output):
		if node is None:
			return level
		height = self.inorder(node.left, level + 1, output)
		output.append((node.data, level))
		height = max(height, self.inorder(node.right, level + 1, output))
		return height

	def shortestRange(self, root):
		nodes = []
		height = self.inorder(root, 0, nodes)
		level_count = [0] * height
		right = -1
		count = 0
		while count < height:
			right += 1
			if level_count[nodes[right][1]] == 0:
				count += 1
			level_count[nodes[right][1]] += 1
		left = 0
		while level_count[nodes[left][1]] > 1:
			level_count[nodes[left][1]] -= 1
			left += 1
		min_ = 0
		max_ = 100000
		while True:
			if nodes[right][0] - nodes[left][0] < max_ - min_:
				min_ = nodes[left][0]
				max_ = nodes[right][0]
			right += 1
			if right == len(nodes):
				return [min_, max_]
			level_count[nodes[right][1]] += 1
			while level_count[nodes[left][1]] > 1:
				level_count[nodes[left][1]] -= 1
				left += 1


class Solution:

	def shortestRange(self, root):
		a = []

		def dfs(node, level):
			if node:
				a.append((node.data, level))
				dfs(node.left, level + 1)
				dfs(node.right, level + 1)
		dfs(root, 0)
		a.sort()
		(n, m) = (max((x for (_, x) in a)) + 1, {})
		(l, r) = (a[0][0], a[-1][0])
		i = 0
		j = 0
		for (j, (_, t)) in enumerate(a):
			m[t] = m.get(t, 0) + 1
			while i < j and len(m) == n:
				if a[j][0] - a[i][0] < r - l:
					(l, r) = (a[i][0], a[j][0])
				if m[a[i][1]] == 1:
					del m[a[i][1]]
				else:
					m[a[i][1]] -= 1
				i += 1
		return [l, r]


from queue import deque
import heapq

class Solution:

	def smallestRange(self, nums):
		(pointers, heap) = ([0 for i in range(len(nums))], [])
		output = [float('inf'), float('-inf')]
		for i in range(len(nums)):
			heapq.heappush(heap, (nums[i][pointers[i]], i))
			output[0] = min(output[0], nums[i][pointers[i]])
			output[1] = max(output[1], nums[i][pointers[i]])
		maxVal = output[1]
		while len(heap) == len(nums):
			top = heapq.heappop(heap)
			ai = top[1]
			if pointers[ai] < len(nums[ai]) - 1:
				pointers[ai] += 1
				heapq.heappush(heap, (nums[ai][pointers[ai]], ai))
				maxVal = max(maxVal, nums[ai][pointers[ai]])
				if output[1] - output[0] > maxVal - heap[0][0]:
					(output[1], output[0]) = (maxVal, heap[0][0])
		return output

	def shortestRange(self, root):
		l = []
		if root == None:
			return []
		q1 = deque()
		q2 = deque()
		q1.append(root)
		while q1:
			a = []
			while q1:
				if q1[0] != None:
					if q1[0].left != None:
						q2.append(q1[0].left)
					if q1[0].right != None:
						q2.append(q1[0].right)
					a.append(q1.popleft().data)
			l.append(a)
			q1 = q2
			q2 = deque()
		return self.smallestRange(l)


class Solution:

	def shortestRange(self, root):
		nums = []
		level_count = {}
		traverse(root, 0, nums, level_count)
		num_levels = len(level_count)
		level_counts = {}
		best_start = 0
		best_end = 999999999999
		i = 0
		j = 0
		while j < len(nums):
			(val, level) = nums[j]
			if level not in level_counts:
				level_counts[level] = 1
			else:
				level_counts[level] += 1
			while i <= j and len(level_counts) == num_levels:
				if nums[j][0] - nums[i][0] < best_end - best_start or (nums[j][0] - nums[i][0] == best_end - best_start and nums[i][0] < best_start):
					best_start = nums[i][0]
					best_end = nums[j][0]
				level_counts[nums[i][1]] -= 1
				if level_counts[nums[i][1]] == 0:
					level_counts.pop(nums[i][1])
				i += 1
			j += 1
		return (best_start, best_end)

def traverse(cur, level, res, level_count):
	if not cur:
		return
	traverse(cur.left, level + 1, res, level_count)
	res.append((cur.data, level))
	if level in level_count:
		level_count[level] += 1
	else:
		level_count[level] = 1
	traverse(cur.right, level + 1, res, level_count)