<p>Given a binary tree, find its minimum depth.</p>

<p>The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.</p>

<p><strong>Note:</strong>&nbsp;A leaf is a node with no children.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg" style="width: 432px; height: 302px;" />
<pre>
<strong>Input:</strong> root = [3,9,20,null,null,15,7]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> root = [2,null,3,null,4,null,5,null,6]
<strong>Output:</strong> 5
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[0, 10<sup>5</sup>]</code>.</li>
	<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>
</ul>

from collections import deque
'''
1. BFS bc it has the short circuit concept where we never "reach" O(n)
2. Change problem to "find first leaf in the binary tree and return its depth"
3. I had a sublist which tracked the current level
    depthValue = [0] -> return depthValue[0]

O(n) time
O(n) space

optimal solution:
O(n) time
O(n) space

"a template" for BFS problems: use tuples to track levels

we have these Levels and we track them via sublists

deque() = [[3], [9,20], ...]

deque() = [3, ,9, 20, 15]

we keep track of the depth through tuples -> [node, depth]
"find first leaf in the binary tree and return its depth"

main
    if size == 0 return 0
    queue = deque((root, 1))

    # run BFS:
    while queue:
        node, depth = queue.popleft()

        # return depth of first leaf node:
        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))

    # we will never hit this
    return 0
[3,9,20,null,null,15,7]

[(3, 1)] 
[ (5, 3), (15,3), (7, 3)]

(? , 4)

optimal solution:  short circuit and tuple carry
O(n) time
O(n) space

'''



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = deque([(root, 1)])

        # run BFS:
        while queue:
            node, depth = queue.popleft()

            # return depth of first leaf node:
            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))
        
43400