Given a binary tree, find the depth of the deepest odd level leaf node in a binary tree. If there is no leaf at odd level then return 0.
Consider that level starts with 1. Depth of a leaf node is number of nodes on the path from root to leaf (including both leaf and root).
Example 1:
Input: 
          1
        /    \
       2      3
      / \    / \
     4   5  6   7
Output: 3
Explanation: In the above tree 4,5,6 and 7 are
odd level leaf nodes at depth 3.So the answer is 3.
Example 2:
Input: 
     1
    / \
    2   4
Output: 0
Your task:
You don't need to read input or print anything. Your task is to complete the function depthOfOddLeaf() which takes root node of the tree as input parameter and returns an integer denoting the maximum depth of a odd level leaf node of the tree. If there is no such leaf node return 0.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=T<=1000
1<=n<=1000
1<=data of node<=1000

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

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

class Solution:
    def depthOfOddLeaf(self,root):
        #code here

Solutions:
class Solution:

	def depthOfOddLeaf(self, root):
		q = []
		q.append(root)
		h = 0
		ans = 0
		while len(q) > 0:
			temp = []
			h += 1
			while len(q) > 0:
				x = q.pop(0)
				temp.append(x)
				if x.left == None and x.right == None and (h % 2 != 0):
					ans = h
			for node in temp:
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
		return ans


class Solution:

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

	def depthOfOddLeaf(self, root):
		l = []
		self.fun(root, 0, l)
		t = -1
		for i in range(len(l)):
			if i % 2 == 0:
				if 'R' in l[i]:
					t = i
		if t == -1:
			return 0
		else:
			return t + 1


class Solution:

	def solve(self, root, l):
		if root == None:
			return
		if root.left == None and root.right == None:
			if l % 2 != 0:
				if self.ans < l:
					self.ans = l
		l += 1
		self.solve(root.left, l)
		self.solve(root.right, l)
		l -= 1

	def depthOfOddLeaf(self, root):
		self.ans = 0
		self.solve(root, 1)
		return self.ans


class Solution:

	def depthOfOddLeaf(self, root):
		ans = 0
		counter = 0
		if root is None:
			return 0
		st = []
		st.append(root)
		while len(st) > 0:
			counter += 1
			t = []
			while len(st) != 0:
				x = st.pop()
				if x.left is None and x.right is None and (counter % 2 != 0):
					ans = counter
				if x.left is not None:
					t.append(x.left)
				if x.right is not None:
					t.append(x.right)
			st = t
		return ans


class Solution:

	def depthOfOddLeaf(self, root):

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

		def ans(root, level):
			if root == None:
				return 0
			left = ans(root.left, level + 1)
			right = ans(root.right, level + 1)
			if check(root) and level % 2 != 0:
				return level
			else:
				return max(left, right)
		return ans(root, 1)


class Solution:

	def __init__(self):
		self.m = 0

	def depthOfOddLeaf(self, root):
		self.solve(root, 1)
		return self.m

	def solve(self, root, l):
		if root == None:
			return
		if root.left == None and root.right == None:
			if l % 2 != 0:
				self.m = max(self.m, l)
			return
		self.solve(root.left, l + 1)
		self.solve(root.right, l + 1)


class Solution:

	def depthOfOddLeaf(self, root):
		queue = deque([(root, 1)])
		height = 0
		while queue:
			(node, h) = queue.popleft()
			if node.left is None and node.right is None and (h % 2 == 1):
				height = max(height, h)
			if node.left is not None:
				queue.append((node.left, h + 1))
			if node.right is not None:
				queue.append((node.right, h + 1))
		return height


class Solution:

	def depthOfOddLeaf(self, root):
		q = []
		q.append(root)
		q.append('$')
		level = 1
		depth = 0
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					q.append('$')
					level += 1
			else:
				if t.left is None and t.right is None and (level % 2 != 0):
					if depth < level:
						depth = level
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return depth


class Solution:

	def depthOfOddLeaf(self, root):
		arr = [0]
		level = 1
		q = []
		q.append(root)
		while len(q) != 0:
			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)
				if node.left == None and node.right == None and (level % 2 == 1):
					arr.append(level)
			level += 1
		return max(arr)


import collections

class Solution:

	def depthOfOddLeaf(self, root):
		level = 1
		q = collections.deque([root])
		ans = 0
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if level % 2 == 1 and (not (node.left or node.right)):
					ans = level
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		return ans


class Solution:

	def depthOfOddLeaf(self, root):

		def traversal(root, level):
			nonlocal maximum
			if root == None:
				return None
			if root.left == None and root.right == None and (level % 2 != 0):
				maximum = max(maximum, level)
			if root.left:
				traversal(root.left, level + 1)
			if root.right:
				traversal(root.right, level + 1)
		level = 1
		maximum = 0
		traversal(root, level)
		return maximum


class Solution:

	def depthOfOddLeaf(self, root):
		global k
		k = 0

		def sol(root, level):
			global k
			if root == None:
				return 0
			if root.left == None and root.right == None and (level % 2 != 0) and (k < level):
				k = level
			sol(root.left, level + 1)
			sol(root.right, level + 1)
			return
		sol(root, 1)
		return k


class Solution:

	def depthOfOddLeaf(self, root):
		return self.oddLevel(root, 0)

	def oddLevel(self, root, level):
		if not root:
			return 0
		level += 1
		if not root.left and (not root.right) and level % 2:
			return level
		left = self.oddLevel(root.left, level)
		right = self.oddLevel(root.right, level)
		return max(left, right)


class Solution:

	def depthOfOddLeaf(self, root):
		d = {}
		level = 1
		self.helper(root, level, d)
		d1 = sorted(d.keys())
		if d1:
			return d1[-1]
		return 0

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


INT_MAX = 2 ** 31

class newNode:

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

def maxOddLevelDepth(root):
	if not root:
		return 0
	q = []
	q.append(root)
	result = 0
	level = 0
	while len(q):
		size = len(q)
		level += 1
		while size > 0:
			temp = q[0]
			q.pop(0)
			if not temp.left and (not temp.right) and (level % 2 != 0):
				result = level
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
			size -= 1
	return result

class Solution:

	def depthOfOddLeaf(self, root):
		return maxOddLevelDepth(root)


def depthOfOddLeafUtil(root, level):
	if root is None:
		return 0
	if root.left is None and root.right is None and level & 1:
		return level
	return max(depthOfOddLeafUtil(root.left, level + 1), depthOfOddLeafUtil(root.right, level + 1))

def depthOfOddLeaf1(root):
	level = 1
	depth = 0
	return depthOfOddLeafUtil(root, level)

class Solution:

	def depthOfOddLeaf(self, root):
		return depthOfOddLeaf1(root)


class Solution:

	def depthOfOddLeaf(self, root):

		def helper(root, mx, k):
			if root:
				if not root.left and (not root.right):
					if k & 1 == 1:
						mx = max(mx, k)
					return mx
				mx = helper(root.left, mx, k + 1)
				mx = helper(root.right, mx, k + 1)
			return mx
		mx = helper(root, -1, 1)
		return mx if mx != -1 else 0


class Solution:

	def depthOfOddLeaf(self, root):

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

		def helper(x):
			ans = []
			q = deque()
			t = []
			if not x:
				return ans
			q.append(x)
			while q:
				for i in range(len(q)):
					a = q.popleft()
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t.append(a)
				ans.append(t)
				t = []
			return ans
		a = helper(root)
		ans = 0
		for i in range(len(a)):
			if i % 2 == 0:
				b = a[i]
				for j in b:
					if leaf(j):
						ans = i + 1
						break
		return ans


class Solution:

	def depthOfOddLeaf(self, root):

		def calculate(root, level):
			if root == None:
				return 0
			elif root.left == None and root.right == None and level & 1:
				return level
			else:
				return max(calculate(root.left, level + 1), calculate(root.right, level + 1))
		return calculate(root, 1)


from collections import deque

class Solution:

	def depthOfOddLeaf(self, root):
		q = deque()
		q.append(root)
		level = 0
		ans = 0
		while len(q) > 0:
			temp = []
			level += 1
			while len(q) > 0:
				curr = q.popleft()
				temp.append(curr)
				if curr.left == curr.right == None and level % 2 != 0:
					ans = level
			for node in temp:
				if node.left != None:
					q.append(node.left)
				if node.right != None:
					q.append(node.right)
		return ans


class Solution:

	def depthOfOddLeaf(self, root):
		q = []
		ans = [0]
		lev = 1
		q.append(root)
		while q:
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if node.left == None and node.right == None:
					if lev % 2 != 0:
						ans.append(lev)
			lev += 1
		return ans[-1]


class Node:

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

class Solution:

	def depthOfOddLeaf(self, root):
		if root is None:
			return None
		else:
			d = {}
			count = 1
			import collections
			q = collections.deque()
			q.append(root)
			while q:
				level = []
				for i in range(len(q)):
					node = q.popleft()
					if node.left == None and node.right == None and (count % 2 != 0):
						ans = count
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				d[count] = level
				count += 1
			try:
				return ans
			except:
				return 0


class Solution:

	def depth(self, root, level):
		if root is None:
			return 0
		if root.left is None and root.right is None and (level % 2 == 1):
			return level
		return max(Solution().depth(root.left, level + 1), Solution().depth(root.right, level + 1))

	def depthOfOddLeaf(self, root):
		level = 1
		maxlevel = Solution().depth(root, level)
		return maxlevel


class Solution:

	def depthOfOddLeaf(self, root):
		m = 0
		q = [[root, 1]]
		c = 0
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			f = 0
			if t.left:
				f = 1
				q.append([t.left, g + 1])
			if t.right:
				f = 1
				q.append([t.right, g + 1])
			if f == 0 and g % 2 == 1:
				if g > m:
					m = g
			c += 1
		return m


class Solution:

	def depthOfOddLeaf(self, root):
		q = [root]
		f = 1
		maxi = 0
		while q:
			cnt = 0
			for i in range(len(q)):
				t = q.pop(0)
				if t.right:
					q.append(t.right)
				if t.left:
					q.append(t.left)
				if not t.right and (not t.left):
					cnt += 1
			if f & 1 and cnt > 0:
				maxi = f
			f += 1
		return maxi


class Solution:

	def depthOfOddLeaf(self, root):
		return self.trying(root, 1)

	def trying(self, root, level):
		if root is None:
			return 0
		if root.left is None and root.right is None and (level % 2 != 0):
			return level
		return max(self.trying(root.left, level + 1), self.trying(root.right, level + 1))
from collections import deque

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = 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

def inord(root):
	if not root:
		return
	inord(root.left)
	print(root.data, end=' ')
	inord(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		root = buildTree(s)
		ob = Solution()
		res = ob.depthOfOddLeaf(root)
		print(res)


class Solution:

	def depthOfOddLeaf(self, root):

		def helper(root, depth):
			if root is None:
				return 0
			if root.left is None and root.right is None and (depth % 2 != 0):
				return depth
			left_depth = helper(root.left, depth + 1)
			right_depth = helper(root.right, depth + 1)
			return max(left_depth, right_depth)
		return helper(root, 1)


class Solution:

	def depthOfOddLeaf(self, root):
		q = []
		q.append(root)
		level = 1
		o = []
		while len(q):
			count = len(q)
			while count > 0:
				p = q.pop(0)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				if p.left == None and p.right == None:
					if level % 2 == 1:
						o.append(level)
				count -= 1
			level += 1
		if len(o) == 0:
			return 0
		else:
			return o[-1]


class Solution:

	def height(self, root, depth=1):
		if root is None:
			return 0
		leftHeight = self.height(root.left, depth + 1)
		rightHeight = self.height(root.right, depth + 1)
		if root.left is None and root.right is None:
			if depth % 2 == 0:
				return -1
			else:
				return depth
		return max(leftHeight, rightHeight)

	def depthOfOddLeaf(self, root):
		depth = self.height(root)
		if depth == -1:
			return 0
		return depth


class Solution:

	def depthofoddleaf(self, root, level):
		if not root:
			return 0
		if root and (not root.left) and (not root.right):
			if level % 2 != 0:
				return level
			else:
				return 0
		levelr = level
		return max(self.depthofoddleaf(root.left, level + 1), self.depthofoddleaf(root.right, levelr + 1))

	def depthOfOddLeaf(self, root):
		l = 1
		return self.depthofoddleaf(root, l)


class Solution:

	def depthOfOddLeaf(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		q = [root]
		l = []
		k = 1
		mini = 0
		while len(q) > 0:
			for node in q:
				if node.left:
					l.append(node.left)
				if node.right:
					l.append(node.right)
				if node.left is None and node.right is None:
					if k % 2 == 1:
						mini = k
			k = k + 1
			q = l
			l = []
		return mini


class Solution:

	def depthOfOddLeaf(self, root):
		if not root:
			return
		level = 0
		return self.depthOfOddLeafUtil(root, level + 1)

	def depthOfOddLeafUtil(self, root, level):
		if not root:
			return 0
		if level % 2 != 0 and self.isLeaf(root):
			return level
		return max(self.depthOfOddLeafUtil(root.left, level + 1), self.depthOfOddLeafUtil(root.right, level + 1))

	def isLeaf(self, root):
		if not root:
			return False
		if not root.left and (not root.right):
			return True
		return False


class Solution:

	def depthOfOddLeaf(self, curr_node):

		def isleaf(curr_node):
			return curr_node.left == None and curr_node.right == None

		def deepestOddLevelDepthUtil(curr_node, curr_level):
			if curr_node == None:
				return 0
			curr_level += 1
			if curr_level % 2 != 0 and isleaf(curr_node):
				return curr_level
			return max(deepestOddLevelDepthUtil(curr_node.left, curr_level), deepestOddLevelDepthUtil(curr_node.right, curr_level))
		return deepestOddLevelDepthUtil(curr_node, 0)


class Solution:

	def depthOfOddLeaf(self, root):
		q = [root]
		level = 0
		ans = 0
		while q:
			level += 1
			n = len(q)
			for i in range(n):
				p = q.pop(0)
				if p.left:
					q.append(p.left)
				if p.right:
					q.append(p.right)
				if level % 2 != 0 and (not p.left) and (not p.right):
					ans = level
		return ans


class Solution:

	def depthOfOddLeaf(self, root):
		q = []
		q.append([root, 1])
		Max = 0
		while q:
			(node, lvl) = q.pop(0)
			if node is not None:
				if node.left is None and node.right is None:
					if lvl % 2 == 1:
						Max = max(Max, lvl)
			if node.left is not None:
				q.append([node.left, lvl + 1])
			if node.right is not None:
				q.append([node.right, lvl + 1])
		return Max


class Solution:

	def depthOfOddLeaf(self, root):
		l = 0
		s = [root]
		ans = 0
		while len(s):
			n = len(s)
			l += 1
			for i in range(n):
				t = s.pop(0)
				if t.left == None and t.right == None and (l % 2 != 0):
					ans = l
				if t.left:
					s.append(t.left)
				if t.right:
					s.append(t.right)
		if ans == 0:
			return 0
		return ans


class Solution:

	def depthOfOddLeaf(self, root):
		if not root:
			return 0
		qu = []
		qu.append(root)
		(c, count) = (1, 0)
		while qu:
			n = len(qu)
			for i in range(n):
				node = qu.pop(0)
				if node.left:
					qu.append(node.left)
				if node.right:
					qu.append(node.right)
				if not node.left and (not node.right) and (c % 2 != 0):
					count = c
			c += 1
		return count


class Solution:

	def helper(self, q, k):
		while len(q) != 0:
			(p, l) = q.pop(0)
			if not p.left and (not p.right):
				if l % 2 == 1:
					k = max(k, l)
			if p.left:
				q.append((p.left, l + 1))
			if p.right:
				q.append((p.right, l + 1))
		return k

	def depthOfOddLeaf(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		return self.helper([(root, 1)], 0)


from collections import defaultdict

class Solution:

	def __init__(self):
		self.ans = [0]

	def depthOfOddLeaf(self, root):
		if root is None:
			return []
		if root.left is None and root.right is None:
			return 1
		d = defaultdict(list)

		def bfs(node, level):
			if not node:
				return
			if level % 2 != 0 and node.left is None and (node.right is None):
				self.ans.append(level)
			d[level].append(node.data)
			bfs(node.left, level + 1)
			bfs(node.right, level + 1)
		bfs(root, 1)
		levels = list(d.keys())
		if levels[-1] > 1 and levels[-1] % 2 != 0:
			return levels[-1]
		else:
			return max(self.ans)


def maxOddLevelDepth(root):
	if not root:
		return 0
	q = []
	q.append(root)
	result = 0
	level = 0
	while len(q):
		size = len(q)
		level += 1
		while size > 0:
			temp = q[0]
			q.pop(0)
			if not temp.left and (not temp.right) and (level % 2 != 0):
				result = level
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
			size -= 1
	return result

class Solution:

	def depthOfOddLeaf(self, root):
		return maxOddLevelDepth(root)


class Solution:

	def depthOfOddLeaf(self, root):
		level = 1
		res = self.depth(root, level)
		return res

	def depth(self, root, level):
		if root == None:
			return 0
		if root.left == None and root.right == None and (level % 2 == 1):
			return level
		LD = self.depth(root.left, level + 1)
		RD = self.depth(root.right, level + 1)
		TD = max(LD, RD)
		return TD


class Solution:

	def depthOfOddLeaf(self, root):
		left = 1
		l = [0]
		cou(root, left, l)
		if max(l) == 0:
			return 0
		else:
			ma = 0
			for i in l:
				if i % 2 != 0:
					ma = max(ma, i)
			return ma

def cou(root, depth, l):
	if root is None:
		return
	if root.left is None and root.right is None and (depth % 2 != 0):
		l.append(depth)
	left = cou(root.left, depth + 1, l)
	right = cou(root.right, depth + 1, l)


class Solution:

	def Depth(self, root, level):
		if root == None:
			return 0
		if root.left == None and root.right == None and (level % 2 == 1):
			return level
		return max(self.Depth(root.left, level + 1), self.Depth(root.right, level + 1))

	def depthOfOddLeaf(self, root):
		level = 1
		return self.Depth(root, level)


from collections import deque

class Solution:

	def depthOfOddLeaf(self, root):
		if root == None:
			return 0
		q = deque()
		q.append([root, 1])
		size = 1
		ans = -float('inf')
		ans = 0
		while size:
			for i in range(size):
				cur = q.popleft()
				size -= 1
				if cur[0].left:
					q.append([cur[0].left, cur[1] + 1])
					size += 1
				if cur[0].right:
					q.append([cur[0].right, cur[1] + 1])
					size += 1
				if cur[0].left == cur[0].right == None and cur[1] & 1:
					ans = max(ans, cur[1])
		return ans


class Solution:

	def depthOfOddLeaf(self, root):
		q = []
		q.append(root)
		level = 0
		k = 0
		while len(q) > 0:
			count = len(q)
			level = level + 1
			for i in range(count):
				node = q.pop(0)
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
				if node.left is None and node.right is None:
					if level % 2 != 0:
						k = level
		return k


import queue

class Solution:

	def height(self, root):
		if root is None:
			return 0
		lh = self.height(root.left)
		rh = self.height(root.right)
		if lh > rh:
			return 1 + lh
		return 1 + rh

	def depthOfOddLeaf(self, root):
		if root is None:
			return 0
		h = self.height(root)
		if h % 2 != 0:
			return h
		else:
			q = queue.Queue()
			q.put(root)
			level = 0
			result = 0
			while q.empty() != True:
				size = q.qsize()
				level += 1
				while size > 0:
					current_node = q.get()
					if current_node.left == None and current_node.right == None and (level % 2 != 0):
						result = level
					if current_node.left != None:
						q.put(current_node.left)
					if current_node.right != None:
						q.put(current_node.right)
					size -= 1
			return result


from collections import deque

class Solution:

	def __init__(self):
		self.res = 0

	def depthOfOddLeaf(self, root):
		self.followUp(root, 1, self.res)
		return self.res

	def followUp(self, root, level, res):
		if root is None:
			return
		if root.left == None and root.right == None and (level & 1 == 1):
			self.res = max(self.res, level)
		self.followUp(root.left, level + 1, res)
		self.followUp(root.right, level + 1, res)