Given a Binary tree. Find the level in binary tree which has the maximum number of nodes.
Example 1:
Input:
      2
    /    \ 
   1      3
 /   \     \
4    6      8
     / 
    5
Output: 2
Explanation: The level 2 with nodes 4,
6 and 8 is the level with maximum
number of nodes. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxNodeLevel() that takes root node of the tree as input and returns an integer which is level of the tree with maximum nodes. The root is at level 0. If two or more levels have same number of maximum nodes , then return smallest level.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1<=Number of level<=10

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: '''

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



# Return the level (0-indexed) with maximum number of nodes.

def maxNodeLevel(root):

    # code here

Solutions:
def maxNodeLevel(root):
	q = [root]
	res = 0
	mx = 0
	lev = 0
	while q:
		l = len(q)
		if l > mx:
			mx = l
			res = lev
		for i in range(l):
			p = q.pop(0)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
		lev += 1
	return res


def maxNodeLevel(root):
	t = k = 0
	i = 0
	queue = [root]
	level = []
	while queue != [] and root is not None:
		l = []
		for node in queue:
			l.append(node.data)
			if node.left:
				level.append(node.left)
			if node.right:
				level.append(node.right)
		if len(l) > t:
			t = len(l)
			k = i
		queue = level
		level = []
		i += 1
	return k


from collections import deque

def maxNodeLevel(root):
	queue = deque()
	queue.append(root)
	level = 0
	max_size = 0
	max_level = 0
	while queue:
		size = len(queue)
		if size > max_size:
			max_size = size
			max_level = level
		for _ in range(size):
			curr = queue.popleft()
			if curr.left:
				queue.append(curr.left)
			if curr.right:
				queue.append(curr.right)
		level = level + 1
	return max_level


def maxNodeLevel(root):
	l = [root, 'a']
	max1 = 0
	res = 0
	c = 0
	while True:
		if len(l) > max1:
			max1 = len(l)
			res = c
		w = l.pop(0)
		while w != 'a':
			if w.left != None:
				l.append(w.left)
			if w.right != None:
				l.append(w.right)
			w = l.pop(0)
		if l == []:
			return res
		c += 1
		l.append('a')


from queue import Queue

def maxNodeLevel(root):
	highest_level = 0
	highest = 0
	q = Queue()
	q.put(root)
	level = 0
	while not q.empty():
		node_count = 0
		next_level = []
		while not q.empty():
			node = q.get()
			node_count += 1
			if node.left:
				next_level.append(node.left)
			if node.right:
				next_level.append(node.right)
		if node_count > highest:
			highest = node_count
			highest_level = level
		level += 1
		for n in next_level:
			q.put(n)
	return highest_level


def maxNodeLevel(root):
	temp = [root]
	s = 1
	l = 0
	res = 0
	while temp:
		r = []
		c = 0
		l += 1
		for i in temp:
			if i.left:
				c += 1
				r.append(i.left)
			if i.right:
				r.append(i.right)
				c += 1
		if c > s:
			s = c
			res = l
		temp = r
	return res


def fun(root, level, l):
	if root == None:
		return
	if level >= len(l):
		l.append([])
	l[level].append(root.data)
	fun(root.left, level + 1, l)
	fun(root.right, level + 1, l)

def maxNodeLevel(root):
	l = []
	fun(root, 0, l)
	(m, t) = (0, 0)
	for i in range(len(l)):
		if len(l[i]) > m:
			m = len(l[i])
			t = i
	return t


from queue import Queue

def maxNodeLevel(root):
	if root == None:
		return None
	q = Queue()
	q.put(root)
	height = 0
	level = maxx = 0
	length = 1
	while q.empty() == False:
		times = length
		if times > maxx:
			maxx = times
			level = height
		length = 0
		for i in range(times):
			root = q.get()
			if root.left != None:
				q.put(root.left)
				length += 1
			if root.right != None:
				q.put(root.right)
				length += 1
		height += 1
	return level


def maxNodeLevel(root):
	if root is None:
		return 0
	q = deque()
	q.append(root)
	current_level = -1
	max_level = 0
	prev_count = 0
	while q:
		count = len(q)
		current_level += 1
		if count > prev_count:
			prev_count = count
			max_level = current_level
		for i in range(count):
			node = q.popleft()
			if node.left is not None:
				q.append(node.left)
			if node.right is not None:
				q.append(node.right)
	return max_level


def maxNodeLevel(root):
	(de, check, ans) = (deque([None, root]), [], [])
	while de:
		x = de.pop()
		if not x:
			if de:
				de.appendleft(None)
			ans.append(check)
			check = []
		else:
			check.append(x.data)
			if x.left:
				de.appendleft(x.left)
			if x.right:
				de.appendleft(x.right)
	check = [len(ans[i]) for i in range(len(ans))]
	return check.index(max(check))


def maxNodeLevel(root):
	l = 0
	q = [root]
	ans = 0
	no = float('-inf')
	while q:
		j = 0
		for i in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			j += 1
		if j > no:
			no = j
			ans = l
		l += 1
	return ans


import collections

def maxNodeLevel(root):
	q = collections.deque()
	q.append(root)
	mx = 0
	level = 0
	ans = 0
	while q:
		qLen = len(q)
		for i in range(qLen):
			cur = q.popleft()
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
		level += 1
		if mx < qLen:
			ans = level
			mx = max(qLen, mx)
	return ans - 1


def maxNodeLevel(root):
	l = []
	q = []
	k = [0]
	m = -1
	q.append(root)
	while q:
		z = q.pop(0)
		x = k.pop(0)
		if m != x:
			m = x
			l.append([])
		l[-1].append(z.data)
		if z.left is not None:
			q.append(z.left)
			k.append(x + 1)
		if z.right is not None:
			q.append(z.right)
			k.append(x + 1)
	return l.index(max(l, key=len))


def maxNodeLevel(root):
	q = [root, 'a']
	ar = 1
	cnt = 0
	ans = 0
	fa = 0
	while len(q) != 0:
		node = q.pop(0)
		if node == 'a':
			ans += 1
			if cnt > ar:
				ar = cnt
				fa = ans
			cnt = 0
			if len(q) == 0:
				break
			q.append('a')
		else:
			if node.left:
				q.append(node.left)
				cnt += 1
			if node.right:
				q.append(node.right)
				cnt += 1
	return fa


def maxNodeLevel(root):
	q = [root, 'a']
	cntNodes = 1
	cntTemp = 0
	level = 0
	ans = 0
	while len(q) != 0:
		node = q.pop(0)
		if node == 'a':
			level += 1
			if cntTemp > cntNodes:
				cntNodes = cntTemp
				ans = level
			if len(q) == 0:
				break
			q.append('a')
			cntTemp = 0
		else:
			if node.left:
				cntTemp += 1
				q.append(node.left)
			if node.right:
				cntTemp += 1
				q.append(node.right)
	return ans


def getT(root, dic, lev):
	if not root:
		return
	try:
		ar = dic[lev]
		ar.append(root.data)
		dic[lev] = ar
	except:
		dic[lev] = [root.data]
	getT(root.left, dic, lev + 1)
	getT(root.right, dic, lev + 1)

def maxNodeLevel(root):
	dic = {}
	getT(root, dic, 0)
	maxx = 0
	lev = -1
	for (i, ar) in dic.items():
		if len(ar) > maxx:
			lev = i
			maxx = len(ar)
	return lev


def maxNodeLevel(root):

	def height(node):
		if node is None:
			return 0
		else:
			lheight = height(node.left)
			rheight = height(node.right)
			if lheight > rheight:
				return lheight + 1
			else:
				return rheight + 1

	def currlvl(root, lvl):
		if root is None:
			return
		elif lvl == 1:
			res.append(root.data)
		elif lvl > 1:
			currlvl(root.left, lvl - 1)
			currlvl(root.right, lvl - 1)
	res = []
	a = []
	h = height(root)
	for i in range(1, h + 1):
		currlvl(root, i)
		a.append(len(res))
		res.clear()
	index = a.index(max(a))
	return index


def maxNodeLevel(root):
	if root is None:
		return 0
	q = []
	q.append(root)
	max = -1
	level = 0
	curr_level = -1
	while len(q) > 0:
		curr_level += 1
		t = []
		if len(q) > max:
			max = len(q)
			level = curr_level
		while len(q) != 0:
			x = q.pop(0)
			if x.left is not None:
				t.append(x.left)
			if x.right is not None:
				t.append(x.right)
		q = t
	return level


def maxNodeLevel(root):

	def helper(root, d, count):
		if root == None:
			return
		if count not in d:
			d[count] = 1
		else:
			d[count] += 1
		if root.left:
			helper(root.left, d, count + 1)
		if root.right:
			helper(root.right, d, count + 1)
	d = {}
	helper(root, d, 0)
	mx = -1
	ans = 0
	for (k, v) in d.items():
		if v > mx:
			mx = v
			ans = k
	return ans


def maxNodeLevel(root):
	x = 0
	q = []
	q.append(root)
	ll = 0
	level = 0
	while q:
		l = len(q)
		lis = []
		for i in range(l):
			temp = q.pop(0)
			lis.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
		if x < len(lis):
			x = len(lis)
			level = ll
		ll += 1
	return level


def maxNodeLevel(root):
	p = []
	q = []
	p.append(0)
	q.append(root)
	g = {}
	while len(q) > 0:
		a = p.pop(0)
		b = q.pop(0)
		if a not in g:
			g[a] = [b.data]
		else:
			g[a].append(b.data)
		if b.left != None:
			p.append(a + 1)
			q.append(b.left)
		if b.right != None:
			p.append(a + 1)
			q.append(b.right)
	maxi = -1
	for x in g:
		if len(g[x]) > maxi:
			maxi = len(g[x])
			r = x
	return r


def maxNodeLevel(root):
	q = deque()
	qLevel = deque()
	q.append(root)
	qLevel.append(0)
	maxData = 1
	maxLevel = 0
	totalLevel = 0
	while len(q) > 0:
		count = len(q)
		totalData = 0
		while count > 0:
			num = q.popleft()
			totalData += 1
			totalLevel = qLevel.popleft()
			if num.left != None:
				q.append(num.left)
				qLevel.append(totalLevel + 1)
			if num.right != None:
				q.append(num.right)
				qLevel.append(totalLevel + 1)
			count -= 1
		if maxData < totalData:
			maxData = totalData
			maxLevel = totalLevel
	return maxLevel


from queue import Queue

def maxNodeLevel(root):
	if root == None:
		return
	level = 0
	count = 0
	maxs = -float('inf')
	q = Queue()
	levelno = 0
	q.put(root)
	while q.qsize() != 0:
		n = q.qsize()
		if n > maxs:
			maxs = n
			levelno = level
		while n != 0:
			node = q.queue[0]
			q.get()
			if node.left != None:
				q.put(node.left)
			if node.right != None:
				q.put(node.right)
			n -= 1
		level += 1
	return levelno


def maxNodeLevel(root):
	q = [root]
	level = 0
	max_level = 0
	max_var = 1
	while len(q) != 0:
		if len(q) > max_var:
			max_level = level
			max_var = len(q)
		for i in range(len(q)):
			node = q.pop(0)
			if node.left != None:
				q.append(node.left)
			if node.right != None:
				q.append(node.right)
		level += 1
	return max_level


import collections

def maxNodeLevel(root):
	maxNodes = 0
	maxLevel = -1
	level = 0
	q = collections.deque([root])
	while q:
		if len(q) > maxNodes:
			maxNodes = len(q)
			maxLevel = level
		for i in range(len(q)):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		level += 1
	return maxLevel


def maxNodeLevel(root):
	res = []
	q = []
	q.append(root)
	while q:
		count = len(q)
		k = []
		while count:
			temp = q.pop(0)
			k.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
			count -= 1
		res.append(k)
	ans = -999
	lev = 0
	for i in range(len(res)):
		if len(res[i]) > ans:
			ans = len(res[i])
			lev = i
	return lev


def maxNodeLevel(root):

	def traversal(root, level):
		if root == None:
			return None
		if level not in dict1:
			dict1[level] = 1
		else:
			dict1[level] += 1
		if root.left:
			traversal(root.left, level + 1)
		if root.right:
			traversal(root.right, level + 1)
	dict1 = dict()
	traversal(root, 0)
	return max(dict1, key=lambda x: dict1[x])


def maxNodeLevel(root):
	q = []
	if root.left is None and root.right is None:
		return 0
	q.append(root)
	q.append('$')
	count = 0
	max = 1
	level = 0
	max_level = 0
	while len(q):
		t = q.pop(0)
		if t == '$':
			if len(q) > 0:
				q.append('$')
				level += 1
				if count > max:
					max = count
					level_max = level
				count = 0
		else:
			if t.left is not None:
				q.append(t.left)
				count += 1
			if t.right is not None:
				q.append(t.right)
				count += 1
	return level_max


from collections import Counter

def maxNodeLevel(root):
	c = Counter()
	myFunc(root, c, 0)
	return c.most_common()[0][0]

def myFunc(root, c, level):
	if not root:
		return
	c[level] += 1
	level += 1
	myFunc(root.left, c, level)
	myFunc(root.right, c, level)
	return


level = {}

def trav(root, l):
	if l in level:
		level[l].append(root.data)
	else:
		level[l] = [root.data]
	if root.left != None:
		trav(root.left, l + 1)
	if root.right != None:
		trav(root.right, l + 1)

def maxNodeLevel(root):
	level.clear()
	trav(root, 0)
	flag = True
	maxL = 0
	res = 0
	for l in level.keys():
		if flag or maxL < len(level[l]):
			flag = False
			maxL = len(level[l])
			res = l
	return res


def maxNodeLevel(root):
	d = {}
	level = 0
	helper(root, level, d)
	l = []
	for i in d:
		l.append(len(d[i]))
	l.sort()
	a = l[-1]
	for i in d:
		if len(d[i]) == a:
			return i

def helper(root, level, d):
	if not root:
		return
	if level not in d:
		d[level] = [root.data]
	else:
		d[level].append(root.data)
	helper(root.left, level + 1, d)
	helper(root.right, level + 1, d)


from queue import Queue

def maxNodeLevel(root):
	if root == None:
		return -1
	q = Queue()
	q.put(root)
	level = 0
	Max = -999999999999
	level_no = 0
	while 1:
		NodeCount = q.qsize()
		if NodeCount == 0:
			break
		if NodeCount > Max:
			Max = NodeCount
			level_no = level
		while NodeCount > 0:
			Node = q.queue[0]
			q.get()
			if Node.left != None:
				q.put(Node.left)
			if Node.right != None:
				q.put(Node.right)
			NodeCount -= 1
		level += 1
	return level_no


def breathFirstSearch(root):
	queue = [root]
	max_ = len(queue)
	level = 1
	max_level = 1
	while len(queue) != 0:
		tmpList = []
		for val in queue:
			if val.left is not None:
				tmpList.append(val.left)
			if val.right is not None:
				tmpList.append(val.right)
		queue = tmpList
		if len(queue) > max_:
			max_ = len(queue)
			max_level = level
		level += 1
	return max_level

def maxNodeLevel(root):
	return breathFirstSearch(root)


def maxNodeLevel(root):

	def helper(root, mp, k):
		if root:
			if k in mp:
				mp[k] += 1
			else:
				mp[k] = 1
			helper(root.left, mp, k + 1)
			helper(root.right, mp, k + 1)
	mp = {}
	helper(root, mp, 0)
	mx = max(list(mp.values()))
	mn = 10000
	for i in mp:
		if mp[i] == mx:
			mn = min(mn, i)
	return mn


def maxNodeLevel(root):
	q = [root]
	num = 0
	level = 0
	while len(q):
		n = len(q)
		if num < n:
			num = n
			result = level
		while n:
			n -= 1
			curr = q[0]
			del q[0]
			if curr.left != None:
				q.append(curr.left)
			if curr.right != None:
				q.append(curr.right)
		level += 1
	return result


def maxNodeLevel(root):
	if root is None:
		return 0
	que = deque()
	que.append(root)
	maxNodes = 0
	maxLevel = 0
	currentLevel = 0
	while len(que) > 0:
		size = len(que)
		if size > maxNodes:
			maxNodes = size
			maxLevel = currentLevel
		for i in range(size):
			node = que.popleft()
			if node.left is not None:
				que.append(node.left)
			if node.right is not None:
				que.append(node.right)
		currentLevel += 1
	return maxLevel


def maxNodeLevel(root):
	levelMap = {}
	if root is None:
		return 0
	fillLevels(root, levelMap, 0)
	maxLevel = -1
	level = -1
	for key in levelMap.keys():
		if maxLevel < levelMap[key]:
			maxLevel = levelMap[key]
			level = key
	return level

def fillLevels(root, levelMap, level):
	if root is None:
		return
	if level in levelMap.keys():
		levelMap[level] += 1
	else:
		levelMap[level] = 1
	fillLevels(root.left, levelMap, level + 1)
	fillLevels(root.right, levelMap, level + 1)


from collections import deque

def maxNodeLevel(root):
	Q = deque()
	maxi = float('-inf')
	level = 0
	res = [maxi, level]
	Q.appendleft(root)
	while Q:
		sz = len(Q)
		if res[0] < sz:
			res[0] = sz
			res[1] = level
		for _ in range(sz):
			node = Q.pop()
			if node.left:
				Q.appendleft(node.left)
			if node.right:
				Q.appendleft(node.right)
		level += 1
	return res[1]


def maxNodeLevel(root):

	def helper(x):
		ans = []
		q = []
		t = 0
		if not x:
			return ans
		q.append(x)
		while q:
			for i in range(len(q)):
				a = q.pop(0)
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
				t += 1
			ans.append(t)
			t = 0
		return ans
	a = helper(root)
	return a.index(max(a))


def maxNodeLevel(root):
	maxi = -float('inf')
	q = [root]
	level = [0, 1]
	while q:
		temp = []
		count = 0
		for i in q:
			count += 1
			if i.left:
				temp.append(i.left)
			if i.right:
				temp.append(i.right)
		if level[1] < count:
			level[1] = count
			level[0] += 1
		q = temp
	return level[0]


import collections
from collections import deque

def maxNodeLevel(root):
	res = []
	a = []
	q = collections.deque()
	q.append(root)
	while q:
		ql = len(q)
		l = []
		for i in range(ql):
			x = q.popleft()
			if x:
				l.append(x.data)
				q.append(x.left)
				q.append(x.right)
		if l:
			res.append(l)
	for i in res:
		a.append(len(i))
	x = max(a)
	y = a.index(x)
	return y


def maxNodeLevel(root):
	global a, m
	m = -1
	a = []

	def S(root, level):
		global a, m
		if not root:
			return 0
		if level > m:
			m = level
			a.append([])
		a[level].append(root.data)
		S(root.left, level + 1)
		S(root.right, level + 1)
	S(root, 0)
	p = -1
	s = 0
	for i in range(len(a)):
		if len(a[i]) > p:
			p = len(a[i])
			s = i
	return s


def maxNodeLevel(root):
	level = 0
	count = -1
	ans = -1
	q = [root]
	while q:
		size = len(q)
		if size > count:
			count = size
			ans = level
		for _ in range(size):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		level += 1
	return ans


import sys

def maxNodeLevel(root):
	if root is None:
		return 0
	(level, max_level) = (0, 0)
	cur_max = -1 * sys.maxsize
	que = [root]
	while que != []:
		temp = []
		count = 0
		for root in que:
			count += 1
			if root.left:
				temp.append(root.left)
			if root.right:
				temp.append(root.right)
		if count > cur_max:
			cur_max = count
			max_level = level
		level += 1
		que = temp
	return max_level


def maxNodeLevel(root):
	q = deque()
	ans = 0
	n = 0
	q.append(root)
	level = 0
	while len(q) > 0:
		temp = []
		while len(q) > 0:
			temp.append(q.popleft())
		if len(temp) > n:
			ans = level
			n = len(temp)
		level += 1
		for node in temp:
			if node.left != None:
				q.append(node.left)
			if node.right != None:
				q.append(node.right)
	return ans


from collections import deque

def maxNodeLevel(root):
	if root is None:
		return None
	q = deque()
	Max = -10
	ans = 0
	l = 0
	q.append(root)
	while q:
		n = len(q)
		if n > Max:
			Max = n
			ans = l
		for i in range(n):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		l = l + 1
	return ans


def maxNodeLevel(root):
	q = []
	dic = {}
	k = []
	l = 0
	q.append(root)
	while q:
		j = []
		for i in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			j.append(node.data)
		if len(j) not in dic:
			dic[len(j)] = l
		l += 1
		k.append(len(j))
	return dic[max(k)]


def maxNodeLevel(root):
	lvl = -1
	queue = []
	queue.append(root)
	maxi = -float('inf')
	maxilvl = -1
	while queue:
		count = len(queue)
		lvl += 1
		if count > maxi:
			maxi = count
			maxilvl = lvl
		for i in range(count):
			curr = queue.pop(0)
			if curr.left:
				queue.append(curr.left)
			if curr.right:
				queue.append(curr.right)
	return maxilvl


from collections import deque

def maxNodeLevel(root):
	q = deque([root])
	(lvl, size) = (0, 0)
	curr_lvl = 0
	while q:
		if len(q) > size:
			lvl = curr_lvl
			size = len(q)
		for _ in range(len(q)):
			node = q.popleft()
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		curr_lvl += 1
	return lvl


def maxNodeLevel(root):
	if root == None:
		return None
	q = [root]
	ans = []
	d = dict()
	k = 0
	while len(q) > 0:
		d[k] = len(q)
		k += 1
		count = len(q)
		for i in range(count):
			temp = q.pop(0)
			ans.append(temp.data)
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
	(ks, vs) = (0, 0)
	for (k, v) in d.items():
		if v > vs:
			(ks, vs) = (k, v)
	return ks


def maxNodeLevel(root):
	level = []
	q = []
	q.append(root)
	while q:
		t = len(q)
		temp = []
		for i in range(t):
			s = q.pop(0)
			if s.right:
				q.append(s.right)
			if s.left:
				q.append(s.left)
			temp.append(s.data)
		level.append(len(temp))
	m = max(level)
	a = level.index(m)
	return a


def maxNodeLevel(root):
	s = {}
	q = [[root, 0]]
	c = 0
	while c != len(q):
		t = q[c][0]
		g = q[c][1]
		if g in s:
			s[g] += 1
		else:
			s[g] = 1
		if t.left:
			q.append([t.left, g + 1])
		if t.right:
			q.append([t.right, g + 1])
		c += 1
	m = 0
	for i in s:
		if s[i] == m:
			if i < j:
				j = i
		if s[i] > m:
			m = s[i]
			j = i
	return j


from collections import deque

def isNode(root):
	if root.left == None and root.right == None:
		return True
	else:
		return False

def maxNodeLevel(root):
	lvl = 0
	if root is None:
		return lvl
	queue = deque()
	queue.append([lvl, root])
	(ans, curr) = (0, -1)
	while len(queue):
		temp = len(queue)
		for i in range(len(queue)):
			(lvl, node) = queue.popleft()
			if node.left:
				queue.append([lvl + 1, node.left])
			if node.right:
				queue.append([lvl + 1, node.right])
		if temp > curr:
			ans = lvl
			curr = temp
	return ans


from collections import *

def maxNodeLevel(root):
	level = 0
	queue = deque()
	queue.append(root)
	maxL = 0
	ans = 0
	while queue:
		if maxL < len(queue):
			maxL = len(queue)
			ans = level
		for _ in range(len(queue)):
			t = queue.popleft()
			if t.left:
				queue.append(t.left)
			if t.right:
				queue.append(t.right)
		level += 1
	return ans


def maxnode(root, level, Dict):
	if root == None:
		return
	if level in Dict:
		Dict[level] += 1
	else:
		Dict[level] = 1
	prevlevel = level
	maxnode(root.left, level + 1, Dict)
	maxnode(root.right, prevlevel + 1, Dict)

def maxNodeLevel(root):
	Dict = {}
	maxnode(root, 0, Dict)
	mx = 0
	ans = 0
	for (i, j) in Dict.items():
		if mx < j:
			mx = j
			ans = i
	return ans


def maxNodeLevel(root):
	ans = [0] * 100000
	helper(ans, root, 0)
	ind = -1
	maxi = 0
	for i in range(len(ans)):
		if ans[i] > maxi:
			maxi = ans[i]
			ind = i
	return ind

def helper(ans, root, d):
	if not root:
		return
	ans[d] += 1
	helper(ans, root.right, d + 1)
	helper(ans, root.left, d + 1)


class Node:

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

def maxNodeLevel(root):
	if root is None:
		return 0
	else:
		d = {}
		count = 0
		import collections
		q = collections.deque()
		q.append(root)
		while q:
			level = []
			for i in range(len(q)):
				node = q.popleft()
				if node:
					level.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			count = count + 1
			d[count] = len(level)
		maxi = max(d.values())
		lst = []
		for key in list(d.keys()):
			if d[key] == maxi:
				lst.append(key - 1)
		return min(lst)


def maxNodeLevel(root):
	q = []
	q.append(root)
	c = 1
	l = 0
	ans = 0
	while len(q):
		n = len(q)
		for i in range(n):
			curr = q.pop(0)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
		if n > c:
			c = n
			ans = l
		l += 1
	return ans


def maxNodeLevel(root):
	q = deque()
	q.append(root)
	arr = []
	maxx = 0
	res = 0
	i = 0
	while q:
		l = len(q)
		temp = []
		for i in range(l):
			x = q.popleft()
			if x.left:
				q.append(x.left)
			if x.right:
				q.append(x.right)
			temp.append(root.data)
		arr.append(temp)
	for i in range(len(arr)):
		if maxx < len(arr[i]):
			maxx = len(arr[i])
			res = i
	return res


def maxNodeLevel(root):
	a = []
	if root == None:
		return a
	q1 = []
	q1.append(root)
	f = 1
	while len(q1) != 0:
		temp = []
		s = len(q1)
		while s > 0:
			t = q1[0]
			temp.append(t.data)
			q1.pop(0)
			if t.left:
				q1.append(t.left)
			if t.right:
				q1.append(t.right)
			s = s - 1
		a.append(temp)
	d = []
	for i in range(len(a)):
		d.append(len(a[i]))
	k = max(d)
	for i in range(len(d)):
		if d[i] == k:
			return i


from collections import deque

def maxNodeLevel(root):
	if root is None:
		return -1
	q = deque()
	q.append(root)
	l = 0
	ans = 0
	maxi = float('-inf')
	while q:
		count = len(q)
		if maxi < count:
			maxi = count
			ans = l
		while count > 0:
			count -= 1
			t = q.popleft()
			if t.left:
				q.append(t.left)
			if t.right:
				q.append(t.right)
		l += 1
	return ans


def maxNodeLevel(root):
	q = [root]
	level = 0
	maxLevel = 0
	maxLen = 0
	while q:
		levelLen = len(q)
		if levelLen > maxLen:
			maxLen = levelLen
			maxLevel = level
		for i in range(levelLen):
			currElem = q.pop(0)
			if currElem.left:
				q.append(currElem.left)
			if currElem.right:
				q.append(currElem.right)
		level += 1
	return maxLevel


def maxNodeLevel(root):
	if root == None:
		return 0
	l1 = []
	l2 = []
	l3 = []
	l1.append(root)
	while l1:
		size = len(l1)
		for i in range(size):
			x = l1[0]
			if x.left is not None:
				l1.append(x.left)
			if x.right is not None:
				l1.append(x.right)
			k = l1.pop(0)
			l2.append(k.data)
		l3.append(l2)
		l2 = []
	res = []
	for i in l3:
		res.append(len(i))
	return res.index(max(res))


from collections import deque

def maxNodeLevel(root):
	if root is None:
		return -1
	q = deque()
	q.append(root)
	l = 0
	ans = 0
	maxi = float('-inf')
	while True:
		count = len(q)
		if count == 0:
			break
		if count > maxi:
			maxi = count
			ans = l
		while count > 0:
			t = q.popleft()
			if t.left != None:
				q.append(t.left)
			if t.right != None:
				q.append(t.right)
			count -= 1
		l += 1
	return ans
from collections import deque
from queue import Queue

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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(maxNodeLevel(root))


def maxNodeLevel(root):
	max_nodes = 0
	max_level = 0
	level = 0
	queue = [root]
	while queue:
		nodes = 0
		n = len(queue)
		for _ in range(n):
			cur = queue.pop(0)
			nodes += 1
			if cur.left:
				queue.append(cur.left)
			if cur.right:
				queue.append(cur.right)
		if nodes > max_nodes:
			max_nodes = nodes
			max_level = level
		level += 1
	return max_level
from collections import deque
from queue import Queue

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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(maxNodeLevel(root))


def lvlOrder(root, m, lvl):
	if root == None:
		return
	lvlOrder(root.left, m, lvl + 1)
	if lvl not in m:
		m[lvl] = 1
	else:
		m[lvl] += 1
	lvlOrder(root.right, m, lvl + 1)

def maxNodeLevel(root):
	m = {}
	ans = -1
	mxNodes = 0
	lvlOrder(root, m, 0)
	for (k, v) in m.items():
		if mxNodes < v:
			ans = k
			mxNodes = v
	return ans
from collections import deque
from queue import Queue

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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(maxNodeLevel(root))


from collections import defaultdict

def solve(root, l, d):
	if root == None:
		return
	solve(root.left, l + 1, d)
	solve(root.right, l + 1, d)
	d[l] += 1

def maxNodeLevel(root):
	l = 0
	d = defaultdict(lambda : 0)
	solve(root, l, d)
	for (k, v) in d.items():
		if v == max(d.values()):
			return k
from collections import deque
from queue import Queue

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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(maxNodeLevel(root))


def maxNodeLevel(root):
	if not root:
		return -1
	q = [root]
	ind = -1
	ll = 1
	res = 0
	while q:
		level = []
		l = len(q)
		ind += 1
		for i in range(l):
			node = q.pop(0)
			if node:
				level.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if level:
			if len(level) > ll:
				ll = len(level)
				res = ind
	return res
from collections import deque
from queue import Queue

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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(maxNodeLevel(root))


def maxNodeLevel(root):

	def dfs(root):
		if root == []:
			return [0]
		l = []
		k = 0
		for i in root:
			if i.left != None:
				l += [i.left]
				k += 1
			if i.right != None:
				l += [i.right]
				k += 1
		return [k] + dfs(list(l))
	l = [1] + dfs([root])
	m = max(l)
	for i in range(len(l)):
		if l[i] == m:
			return i


def maxNodeLevel(root):
	if root is None:
		return
	queue = []
	a = []
	max_ans = 0
	queue.append(root)
	l = 0
	level = 0
	while len(queue) > 0:
		count = len(queue)
		ans = []
		while count > 0:
			temp = queue.pop(0)
			ans.append(temp.data)
			if temp.left:
				queue.append(temp.left)
			if temp.right:
				queue.append(temp.right)
			count -= 1
		count_ans = len(ans)
		l = l + 1
		if max_ans < count_ans:
			max_ans = count_ans
			level = l
		a.append(ans)
	return level - 1


def maxNodeLevel(root):
	q = [root, None]
	k = 0
	count = 0
	mc = 0
	level = 0
	while q:
		t = q.pop(0)
		if not t and q:
			q.append(None)
		elif not t and (not q):
			break
		else:
			if t.left:
				q.append(t.left)
			if t.right:
				q.append(t.right)
			count += 1
			if q[0] == None:
				if mc < count:
					mc = max(mc, count)
					level = k
				k += 1
				count = 0
	return level
from collections import deque
from queue import Queue

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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(maxNodeLevel(root))


def maxNodeLevel(root):
	import collections
	q = collections.deque()
	q.append(root)
	lvl = 0
	rn = 0
	ans = 0
	while q:
		temp = []
		for i in range(len(q)):
			node = q.popleft()
			temp.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		lvl = lvl + 1
		if len(temp) > ans:
			ans = len(temp)
			rn = lvl
	return rn - 1
from collections import deque
from queue import Queue

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__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		print(maxNodeLevel(root))


from collections import deque

def maxNodeLevel(root):
	q = deque()
	q.append(root)
	level = 0
	max_size = 0
	max_level = 0
	while q:
		cur_size = len(q)
		if cur_size > max_size:
			max_size = cur_size
			max_level = level
		while cur_size > 0:
			node = q.popleft()
			cur_size -= 1
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		level += 1
	return max_level


def maxNodeLevel(root):
	level = 0
	if not root:
		return 0
	mapp = {}
	getNodesInLevels(root, mapp, level)
	ans = [k for (k, v) in sorted(mapp.items(), key=lambda x: x[1], reverse=True)]
	return ans[0]

def getNodesInLevels(root, mapp, level):
	if not root:
		return
	if level not in mapp:
		mapp[level] = 0
	mapp[level] += 1
	getNodesInLevels(root.left, mapp, level + 1)
	getNodesInLevels(root.right, mapp, level + 1)


import sys
mp = {}

def height(root, h):
	if not root:
		return
	if h in mp:
		mp[h] += 1
	else:
		mp[h] = 1
	height(root.left, h + 1)
	height(root.right, h + 1)

def maxNodeLevel(root):
	if not root:
		return 0
	mp.clear()
	height(root, 0)
	res = sys.maxsize
	maxlen = 0
	for key in sorted(mp):
		if mp[key] > maxlen:
			maxlen = mp[key]
			res = key
	return res


def maxNodeLevel(root):
	q = []
	(ans, c) = (0, 0)
	q.append(root)
	while q:
		if len(q) > ans:
			ans = max(len(q), ans)
			level = c
		c += 1
		for i in range(len(q)):
			curr = q.pop(0)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
	return level


def levelItemCount(root, level, d):
	if root is None:
		return
	if level in d:
		prevCount = d[level]
		d.update({level: prevCount + 1})
	else:
		d.update({level: 1})
	levelItemCount(root.left, level + 1, d)
	levelItemCount(root.right, level + 1, d)

def maxNodeLevel(root):
	d = dict()
	levelItemCount(root, 0, d)
	max_val = 0
	max_key = 0
	for (key, value) in d.items():
		if value > max_val:
			max_val = int(value)
			max_key = key
	return max_key


def maxNodeLevel(root):
	l = []
	q = []
	q.append(root)
	level = 0
	while len(q):
		count = len(q)
		l.append(len(q))
		while count > 0:
			p = q.pop(0)
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
			count -= 1
	for i in range(len(l)):
		if l[i] == max(l):
			return i


def maxNodeLevel(root):
	lvl = 0
	rlvl = 0
	maxi = 1 if root else 0
	stk = [root]
	while stk:
		q = []
		while stk:
			top = stk.pop()
			if top.left:
				q.append(top.left)
			if top.right:
				q.append(top.right)
		lvl += 1
		if len(q) > maxi:
			rlvl = lvl
			maxi = len(q)
		stk = q
	return rlvl


def maxNodeLevel(root):
	q = []
	maxi = -9999
	q.append(root)
	l = 0
	while q:
		l += 1
		if len(q) > maxi:
			maxi = len(q)
			ans = l
		for i in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
	return ans - 1


from queue import Queue

def maxNodeLevel(root):
	q = Queue()
	if not root:
		return -1
	q.put(root)
	level = 0
	levno = 0
	maxl = -999
	while q.qsize() > 0:
		qsize = q.qsize()
		if maxl < qsize:
			maxl = qsize
			levno = level
		while qsize > 0:
			temp = q.get()
			if temp.left:
				q.put(temp.left)
			if temp.right:
				q.put(temp.right)
			qsize -= 1
		level += 1
	return levno


def maxNodeLevel(root):
	q = []
	lvl = -1
	m = 0
	s = 0
	q.append(root)
	while len(q) > 0:
		lvl += 1
		k = len(q)
		if s < len(q):
			s = len(q)
			m = lvl
		while k > 0:
			node = q[0]
			q.pop(0)
			if node.left != None:
				q.append(node.left)
			if node.right != None:
				q.append(node.right)
			k -= 1
	return m


from collections import deque

def maxNodeLevel(root):
	max_nodes = 0
	max_level = 0
	if not root:
		return max_nodes
	q = deque()
	q.append(root)
	level = 0
	while q:
		count = 0
		for _ in range(len(q)):
			node = q.popleft()
			count += 1
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		if count > max_nodes:
			max_nodes = count
			max_level = level
		level += 1
	return max_level