```
class Solution:
# @param root, a tree node
# @return an integer
def minDepth(self, root):
to_be_explored = collections.deque()
visited = []
count = 0
if root == None:
return 0
to_be_explored.appendleft(root)
visited.append(root)
while to_be_explored:
node = to_be_explored.pop()
count += 1
if node.right != None and node.right not in visited: #<-----this check is O(n)
to_be_explored.appendleft(node.right)
visited.append(node.right)
if node.left != None and node.left not in visited: : #<-----this check is O(n)
to_be_explored.appendleft(node.left)
visited.append(node.left)
return count
```