Given a binary tree, find its minimum depth.
Example 1:
Input:
            1
          /   \
         3     2
        /
       4           
Output: 2
Explanation:
Minimum depth is between nodes 1 and 2 since
minimum depth is defined as  the number of 
nodes along the shortest path from the root 
node down to the nearest leaf node.
Example 2:
Input:
             10
          /     \
        20       30
          \        \   
          40        60 
                   /
                  2 
Output: 3
Explanation:
Minimum depth is between nodes 10,20 and 40.
Your Task:  
You don't need to read input or print anything. Complete the function minDepth() which takes the root node as an input parameter and returns the minimum depth.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of the tree)
 
Constraints:
1 ≤ N ≤ 10^5

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

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

class Solution:
    def minDepth(self, root):
        #Code here

Solutions:
class Solution:

	def minDepth(self, root):
		if root == None:
			return 0
		if not root.left and (not root.right):
			return 1
		if not root.right:
			return self.minDepth(root.left) + 1
		if not root.left:
			return self.minDepth(root.right) + 1
		rightDepth = self.minDepth(root.right)
		leftDepth = self.minDepth(root.left)
		return min(rightDepth, leftDepth) + 1


class Solution:

	def minDepth(self, node):
		if node is None:
			return 0
		elif node.left is None and node.right is None:
			return 1
		elif node.left is None:
			return self.minDepth(node.right) + 1
		elif node.right is None:
			return self.minDepth(node.left) + 1
		else:
			return min(self.minDepth(node.left), self.minDepth(node.right)) + 1


class Solution:

	def minDepth(self, root):

		def t(rt, lev):
			if rt is None:
				return 1000000000.0
			if rt.left is None and rt.right is None:
				return lev + 1
			return min(t(rt.left, lev + 1), t(rt.right, lev + 1))
		return t(root, 0)


class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		min_depth = -1
		s = [(root, 1)]
		while len(s) > 0:
			(curr, depth) = s.pop()
			if not curr.left and (not curr.right) and (min_depth == -1 or min_depth > depth):
				min_depth = depth
			if curr.left:
				s.append((curr.left, depth + 1))
			if curr.right:
				s.append((curr.right, depth + 1))
		return min_depth


import math

class Solution:

	def depth(self, root):
		if root is None:
			return 1000000000.0
		if root.left is None and root.right is None:
			return 1
		return 1 + min(self.depth(root.left), self.depth(root.right))

	def minDepth(self, root):
		return self.depth(root)


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return 1
		if root.left is None:
			return self.minDepth(root.right) + 1
		if root.right is None:
			return self.minDepth(root.left) + 1
		return min(self.minDepth(root.left), self.minDepth(root.right)) + 1


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		q = []
		q.append({'node': root, 'depth': 1})
		while len(q):
			q_item = q.pop(0)
			node = q_item['node']
			depth = q_item['depth']
			if node.left != None:
				q.append({'node': node.left, 'depth': depth + 1})
			if node.right != None:
				q.append({'node': node.right, 'depth': depth + 1})
			if node.right == None and node.left == None:
				return depth


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		lh = self.minDepth(root.left)
		rh = self.minDepth(root.right)
		if root.left and root.right:
			return 1 + min(lh, rh)
		elif root.left:
			return 1 + lh
		else:
			return 1 + rh


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		stack = [(root, 1)]
		result = []
		seen_vals = set()
		while stack:
			(node, lvl) = stack.pop()
			if node.left is None and node.right is None:
				if lvl not in seen_vals:
					seen_vals.add(lvl)
					result.append(lvl)
			if node.left:
				stack.append((node.left, lvl + 1))
			if node.right:
				stack.append((node.right, lvl + 1))
		return min(result)


import sys

class Solution:

	def minDepth(self, root):
		if root is None:
			return 0

		def fun(root, level):
			if root is None:
				return level
			if root.left is None and root.right is None:
				return level
			if root.left:
				left = fun(root.left, level + 1)
			else:
				left = 1000000000
			if root.right:
				right = fun(root.right, level + 1)
			else:
				right = 1000000000
			mini = min(left, right)
			return mini
		level = 1
		re = fun(root, level)
		return re


class Solution:

	def minDepth(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		left = self.minDepth(root.left)
		right = self.minDepth(root.right)
		if left == 0 or right == 0:
			return 1 + (right if left == 0 else left)
		return 1 + min(left, right)


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		else:
			l = self.minDepth(root.left)
			r = self.minDepth(root.right)
			if root.left and root.right:
				return min(l, r) + 1
			elif root.left:
				return l + 1
			else:
				return r + 1


class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		queue = [(root, 1)]
		while queue:
			(node, depth) = queue.pop(0)
			if not node.left and (not node.right):
				return depth
			if node.left:
				queue.append((node.left, depth + 1))
			if node.right:
				queue.append((node.right, depth + 1))
		return 0


class Solution:

	def fun(self, root, level, m):
		if root == None:
			return
		if root.left == None and root.right == None:
			m[0] = min(m[0], level)
		self.fun(root.left, level + 1, m)
		self.fun(root.right, level + 1, m)

	def minDepth(self, root):
		if root == None:
			return 0
		m = []
		m.append(1000000)
		self.fun(root, 1, m)
		return m[0]


class Solution:

	def minDepth(self, root):
		if root == None:
			return 10 ** 26
		if root.left == None and root.right == None:
			return 1
		l = self.minDepth(root.left)
		r = self.minDepth(root.right)
		if l < r:
			return l + 1
		else:
			return r + 1


class Solution:

	def solve(self, root, l, dic):
		if root == None:
			return
		if root.left == None and root.right == None:
			dic.append(l)
		l += 1
		self.solve(root.left, l, dic)
		self.solve(root.right, l, dic)

	def minDepth(self, root):
		if root == None:
			return 0
		dic = []
		self.solve(root, 1, dic)
		ans = float('inf')
		for i in dic:
			ans = min(ans, i)
		return ans


class Solution:

	def minDepth(self, root):
		q = [root]
		l = [1]
		while q:
			z = q.pop(0)
			lev = l.pop(0)
			if z.left is None and z.right is None:
				return lev
			if z.left:
				q.append(z.left)
				l.append(lev + 1)
			if z.right:
				q.append(z.right)
				l.append(lev + 1)


class Solution:

	def minDepth(self, root):
		from collections import deque
		c = 0
		q = deque()
		if root:
			q.append(root)
			c = 1
		while q:
			size = len(q)
			for i in range(size):
				node = q.popleft()
				if node.left or node.right:
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				else:
					return c
			c += 1
		return c


class Solution:

	def depth(self, root, lvl, ans):
		if not root:
			return
		self.depth(root.left, lvl + 1, ans)
		self.depth(root.right, lvl + 1, ans)
		if not root.left and (not root.right):
			ans.append(lvl)

	def minDepth(self, root):
		ans = []
		self.depth(root, 0, ans)
		ans.sort()
		return ans[0] + 1


from queue import Queue

class Solution:

	def minDepth(self, root):
		max_depth = 1
		bfs_queue = Queue()
		bfs_queue.put(root)
		while True:
			children_queue = Queue()
			while not bfs_queue.empty():
				node = bfs_queue.get()
				if node.left is None and node.right is None:
					return max_depth
				if node.left is not None:
					children_queue.put(node.left)
				if node.right is not None:
					children_queue.put(node.right)
			bfs_queue.queue = children_queue.queue
			max_depth += 1


class Solution:

	def minDepth(self, root):
		stack = []
		l = []
		ans = []
		if root is None:
			return

		def help(root, stack, ans):
			if root is None:
				return
			stack.append(root.data)
			if root.left is None and root.right is None:
				ans.append(stack.copy())
				stack.pop()
				return
			help(root.left, stack, ans)
			help(root.right, stack, ans)
			stack.pop()
			return ans
		help(root, stack, ans)
		for i in ans:
			l.append(len(i))
		return min(l)


class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		left = self.minDepth(root.left)
		right = self.minDepth(root.right)
		minn = min(left, right) + 1
		maxx = max(left, right) + 1
		if minn == 1 and maxx > 1:
			return maxx
		return minn


class Solution:

	def minDepth(self, root):
		import sys
		if not root.left and (not root.right):
			return 1
		a = sys.maxsize
		if root.left:
			a = self.minDepth(root.left)
		b = sys.maxsize
		if root.right:
			b = self.minDepth(root.right)
		return 1 + min(a, b)


class Solution:

	def minDepth(self, root):
		bfs = 1
		if not root:
			return 0
		queue = deque([])
		queue.append(root)
		while queue:
			size = len(queue)
			for i in range(size):
				curritem = queue.popleft()
				if curritem.left is None and curritem.right is None:
					return bfs
				if curritem.left is not None:
					queue.append(curritem.left)
				if curritem.right is not None:
					queue.append(curritem.right)
			bfs += 1


class Solution:

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


class Solution:

	def minDepth(self, root):
		minimum = float('inf')

		def dfs(node, level):
			if not node.left and (not node.right):
				nonlocal minimum
				minimum = min(minimum, level)
				return
			if node.left:
				dfs(node.left, level + 1)
			if node.right:
				dfs(node.right, level + 1)
		if not root:
			return 0
		dfs(root, 1)
		return minimum


from collections import deque

class Solution:

	def minDepth(self, root):
		if not root:
			return 1
		q = deque()
		q.append(root)
		minn = 1
		while q:
			l = len(q)
			for i in range(len(q)):
				k = q.popleft()
				if not k.left and (not k.right):
					return minn
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
			minn += 1


class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		q = [root]
		c = 0
		while q:
			le = len(q)
			for i in range(le):
				k = q.pop(0)
				if not k.right and (not k.left):
					return c + 1
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
			c += 1


class Solution:

	def minDepth(self, root):
		return self.help(root)

	def help(self, node):
		if not node:
			return 0
		l = self.help(node.left)
		r = self.help(node.right)
		if l != 0 and r != 0:
			return 1 + min(l, r)
		elif l == 0:
			return 1 + r
		elif r == 0:
			return 1 + l
		else:
			return 1


class Solution:

	def minDepth(self, root):
		if root == None:
			return 0
		l = self.minDepth(root.left)
		r = self.minDepth(root.right)
		if l == 0 or r == 0:
			return max(l, r) + 1
		else:
			return min(l, r) + 1


class Solution:

	def mn(self, root):
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		if root.left:
			lh = self.mn(root.left)
		else:
			lh = float('inf')
		if root.right:
			rh = self.mn(root.right)
		else:
			rh = float('inf')
		return min(lh, rh) + 1

	def minDepth(self, root):
		return self.mn(root)


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		left_height = self.minDepth(root.left)
		right_height = self.minDepth(root.right)
		if left_height == 0 or right_height == 0:
			return max(right_height, left_height) + 1
		else:
			return min(right_height, left_height) + 1


class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		if not root.left and (not root.right):
			return 1
		if not root.left and root.right:
			return 1 + self.minDepth(root.right)
		if root.left and (not root.right):
			return 1 + self.minDepth(root.left)
		else:
			return 1 + min(self.minDepth(root.left), self.minDepth(root.right))


from math import inf

class Solution:

	def __init__(self):
		self.ans = inf

	def tra(self, root, h=1):
		if root == None:
			return
		if root.left == root.right == None:
			self.ans = min(self.ans, h)
		self.tra(root.left, h + 1)
		self.tra(root.right, h + 1)

	def minDepth(self, root):
		self.tra(root)
		return self.ans


class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		minDepth = 1
		q = [root]
		while q:
			for _ 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 is None and node.right is None:
					return minDepth
			minDepth += 1


class Solution:

	def minDepth(self, root):

		def height(root, k):
			if root == None:
				return 0
			if root.right == None and root.left == None:
				self.ans = min(self.ans, k)
			height(root.left, k + 1)
			height(root.right, k + 1)
		self.ans = 999999
		height(root, 0)
		return self.ans + 1


class Solution:

	def bruteforceR(self, root):
		if root:
			left = self.bruteforceR(root.left)
			right = self.bruteforceR(root.right)
			if left == 0 or right == 0:
				return 1 + max(left, right)
			return 1 + min(left, right)
		return 0

	def minDepth(self, root):
		return self.bruteforceR(root)


class Solution:

	def __init__(self):
		self.m = float('inf')

	def minDepth(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:
			self.m = min(self.m, l)
			return
		self.solve(root.left, l + 1)
		self.solve(root.right, l + 1)


class Solution:

	def minDepth(self, root):
		queue = deque([(root, 1)])
		height = 10000000
		while queue:
			(node, h) = queue.popleft()
			if node.left is None and node.right is None:
				return 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 minDepth(self, root):
		level = 0
		q = [root]
		while len(q) != 0:
			check = 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)
				if node.left == None and node.right == None:
					check = 1
			level += 1
			if check == 1:
				break
		return level


import collections

class Solution:

	def minDepth(self, root):
		q = collections.deque([root])
		depth = 1
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if not (node.left or node.right):
					return depth
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			depth += 1


class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		left = self.minDepth(root.left)
		right = self.minDepth(root.right)
		res = min(left, right)
		if left == 0:
			res = right
		if right == 0:
			res = left
		return 1 + res


class Solution:

	def minDepth(self, root):
		if root == None:
			return 0
		a = self.minDepth(root.left)
		b = self.minDepth(root.right)
		if a == 0 or b == 0:
			return max(a, b) + 1
		else:
			return min(a, b) + 1


class Solution:

	def minDepth(self, root):
		s = []
		arr = []
		res = 999999
		s.append([root, 1])
		while s:
			t = s.pop()
			if t[0].left:
				s.append([t[0].left, t[1] + 1])
			if t[0].right:
				s.append([t[0].right, t[1] + 1])
			if not t[0].left and (not t[0].right):
				res = min(res, t[1])
		return res


from collections import deque

class Solution:

	def minDepth(self, root):
		if root == None:
			return 0
		q = deque()
		q.append(root)
		ans = 0
		while q:
			ans += 1
			l = len(q)
			for i in range(l):
				currentNode = q.popleft()
				if currentNode.right == None and currentNode.left == None:
					return ans
				if currentNode.right:
					q.append(currentNode.right)
				if currentNode.left:
					q.append(currentNode.left)


class Solution:

	def minDepth(self, root):
		A = [100000000]
		self.x(root, A, 1)
		return A[0]

	def x(self, root, A, height):
		if root is None:
			return
		if root.left is None and root.right is None:
			if height < A[0]:
				A[0] = height
				return
		self.x(root.left, A, height + 1)
		self.x(root.right, A, height + 1)
		return


class Solution:

	def minDepth(self, root):
		q = deque()
		maxa = 0
		q.append(root)
		lis = []
		l = 1
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if node.left == None and (not node.right):
					lis.append(l)
			l += 1
		return min(lis)


class Solution:

	def minDepth(self, root):
		q = deque()
		q.append(root)
		l = 1
		lis = []
		while q:
			for i in range(len(q)):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if node.left == None and node.right == None:
					lis.append(l)
			l += 1
		liis = set(lis)
		return min(liis)


class Solution:

	def minDepth(self, root):
		return self.dfsDepth(root)

	def dfsDepth(self, root):
		res = float('inf')
		if root:
			if not root.left and (not root.right):
				res = 1
			else:
				depthL = self.dfsDepth(root.left)
				depthR = self.dfsDepth(root.right)
				res = 1 + min(depthL, depthR)
		return res


class Solution:

	def minDepth(self, root):
		level = 1
		q = []
		leaf = {}
		q.append(root)
		q.append('$')
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					level += 1
					q.append('$')
			else:
				if t.left is None and t.right is None:
					leaf[t] = level
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
		return min(leaf.values())


class Solution:

	def minDepth(self, root):
		k = 0
		f = 0
		if root == None:
			return 0
		k = self.minDepth(root.left)
		f = self.minDepth(root.right)
		if root.left and root.right:
			return min(f, k) + 1
		elif root.left:
			return k + 1
		else:
			return f + 1


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		self.min_depth = float('inf')
		curr_depth = 0
		self.chooseMinDepth(root, curr_depth)
		return self.min_depth

	def chooseMinDepth(self, currentNode, curr_depth):
		if currentNode is None:
			return
		if not currentNode.left and (not currentNode.right):
			self.min_depth = min(self.min_depth, curr_depth + 1)
		self.chooseMinDepth(currentNode.left, curr_depth + 1)
		self.chooseMinDepth(currentNode.right, curr_depth + 1)


from collections import deque

class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		queue = deque()
		queue.append(root)
		nodesCount = 1
		level = 1
		while queue:
			for i in range(len(queue)):
				currentNode = queue.popleft()
				if currentNode.left is None and currentNode.right is None:
					return level
				else:
					if currentNode.left:
						queue.append(currentNode.left)
					if currentNode.right:
						queue.append(currentNode.right)
			level += 1
		return level


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		self.depth = float('inf')
		self.helper(root, 0)
		return self.depth

	def helper(self, root, cur_depth):
		if root is None:
			return
		if not root.left and (not root.right):
			self.depth = min(self.depth, cur_depth + 1)
		self.helper(root.left, cur_depth + 1)
		self.helper(root.right, cur_depth + 1)


class Solution:

	def minDepth(self, root):
		m = 0
		if root == None:
			return m
		q = deque([root])
		while q:
			m += 1
			for i in range(len(q)):
				curr = q.popleft()
				if curr.left == None and curr.right == None:
					return m
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
		return m


class Solution:

	def minDepth(self, root):
		level = 0
		mini = float('inf')
		return self.Depth(root, level, mini)

	def Depth(self, root, level, mini):
		if not root:
			return mini
		level += 1
		if root.left is None and root.right is None:
			return min(mini, level)
		mini = self.Depth(root.left, level, mini)
		mini = self.Depth(root.right, level, mini)
		return mini


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		t = 0
		y = [root]
		while y:
			h = y
			y = []
			while h:
				f = h.pop()
				if f == None:
					continue
				if f.right == None and f.left == None:
					return t + 1
				else:
					y.append(f.right)
					y.append(f.left)
			t += 1


class Solution:

	def minDepth(self, root):
		if root is None:
			return 0
		q = []
		q.append({'node': root, 'depth': 1})
		while len(q) > 0:
			queueItem = q.pop(0)
			node = queueItem['node']
			depth = queueItem['depth']
			if node.left is None and node.right is None:
				return depth
			if node.left is not None:
				q.append({'node': node.left, 'depth': depth + 1})
			if node.right is not None:
				q.append({'node': node.right, 'depth': depth + 1})
		t = 0
		y = [root]
		while y:
			h = y
			y = []
			while h:
				f = h.pop()
				if f == None:
					return t
				else:
					y.append(f.right)
					y.append(f.left)
			t += 1


import math

class Solution:

	def minDepth(self, root):
		if root == None:
			return 0
		l = self.minDepth(root.left)
		r = self.minDepth(root.right)
		if l == 0:
			return r + 1
		if r == 0:
			return l + 1
		else:
			return min(l, r) + 1


class Solution:

	def minDepth(self, root):
		min_depth = 0
		if root is None:
			return min_depth
		queue = []
		queue.append(root)
		while len(queue) != 0:
			min_depth += 1
			l1 = len(queue)
			for i in range(l1):
				node = queue.pop(0)
				if node.left is None and node.right is None:
					return min_depth
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return min_depth


class Solution:

	def helper(self, root):
		if root is None:
			return 10 ** 9
		if not root.right and (not root.left):
			return 1
		return 1 + min(self.helper(root.left), self.helper(root.right))

	def minDepth(self, root):
		return self.helper(root)


import sys

class Solution:

	def minDepth(self, root):
		if root.left is None and root.right is None:
			return 1
		q = [root]
		c = 1
		mi = sys.maxsize
		while len(q):
			l = len(q)
			for i in range(l):
				if len(q) != 0:
					x = q.pop(0)
					if x.left is None and x.right is None:
						mi = min(mi, c)
					if i == l - 1:
						c += 1
					if x.left:
						q.append(x.left)
					if x.right:
						q.append(x.right)
		return mi


import queue

class Solution:

	def minDepth(self, root):
		nodes_level = queue.Queue()
		nodes_level.put(root)
		depth = 0
		while True:
			nodes_next_level = queue.Queue()
			depth += 1
			while not nodes_level.empty():
				l = nodes_level.get()
				if l.left is not None:
					nodes_next_level.put(l.left)
				if l.right is not None:
					nodes_next_level.put(l.right)
				if l.left == None and l.right == None:
					return depth
			nodes_level = nodes_next_level


class Solution:

	def minDepth(self, root):
		self.x = []
		self.s = 0

		def x(root):
			if root:
				self.s += 1
				if not root.left and (not root.right):
					self.x.append(self.s)
				x(root.left)
				x(root.right)
				self.s -= 1
		x(root)
		return min(self.x) if self.x else 0


class Solution:

	def minDepth(self, root):
		d = {}
		l = []
		level = 1
		self.helper(root, level, d)
		d1 = sorted(d.keys())
		return min(d1)

	def helper(self, root, level, d):
		if not root:
			return
		if not root.left and (not root.right):
			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)


def minDepth1(root):
	if root is None:
		return 0
	q = []
	q.append({'node': root, 'depth': 1})
	while len(q) > 0:
		queueItem = q.pop(0)
		node = queueItem['node']
		depth = queueItem['depth']
		if node.left is None and node.right is None:
			return depth
		if node.left is not None:
			q.append({'node': node.left, 'depth': depth + 1})
		if node.right is not None:
			q.append({'node': node.right, 'depth': depth + 1})

class Solution:

	def minDepth(self, root):
		return minDepth1(root)


class Solution:

	def minDepth(self, root):

		def getDepth(root):
			if root == None:
				return float('inf')
			if root.left == None and root.right == None:
				return 1
			a = getDepth(root.left)
			b = getDepth(root.right)
			return 1 + min(a, b)
		return getDepth(root)


def hig(root):
	if root == None:
		return 0
	l = hig(root.left)
	r = hig(root.right)
	minn = min(l, r) + 1
	maxx = max(l, r) + 1
	if minn == 1 and maxx > 1:
		return maxx
	return minn

class Solution:

	def minDepth(self, root):
		return hig(root)


from collections import deque

class Solution:

	def minDepth(self, root):
		if not root:
			return 0
		q = deque()
		q.append({'node': root, 'depth': 1})
		while len(q) > 0:
			queueItem = q.popleft()
			node = queueItem['node']
			depth = queueItem['depth']
			if node.left is None and node.right is None:
				return depth
			if node.left is not None:
				q.append({'node': node.left, 'depth': depth + 1})
			if node.right is not None:
				q.append({'node': node.right, 'depth': depth + 1})
		return 0


class Solution:

	def minDepth(self, root):
		if not root:
			return float('inf')
		if root.left is None and root.right is None:
			return 1
		leftNode = self.minDepth(root.left)
		rightNode = self.minDepth(root.right)
		return 1 + min(leftNode, rightNode)


class Solution:

	def minDepth(self, root):

		def dfs(root):
			if root is None:
				return 0
			l = dfs(root.left)
			r = dfs(root.right)
			if l == 0:
				return r + 1
			if r == 0:
				return l + 1
			return min(l, r) + 1
		return dfs(root)