Binary Tree Min Depth - Breadth First Search / BFS on Tree

Problems
1

https://algo.monster/problems/binary_tree_min_depth

2

There’s a problem of the answer of test case 1, it should be 5 instead of 2. As node 2 had two children 4 and 5, it is not a leave node.

3

the question doesn’t explicitly state it but you should return the depth, not the node itself

1 Like
4 
we could also keep track of the depth in the q itself

q = deque([[root, 0]])

while q:

    node, level = q.popleft()

    if not node.left and not node.right:

        return level

    if node.left:

        q.append([node.left, level + 1])

    if node.right:

        q.append([node.right, level + 1])
5

for any go people:

type NodeQueue []Node

func (q *NodeQueue) Enqueue(n Node) {
	*q = append(*q, n)
}

func (q *NodeQueue) Dequeue() Node {
	el := (*q)[0]
	*q = (*q)[1:]

	return el
}

func isLeafNode(n Node) bool {
	if n.left == nil && n.right == nil {
		return true
	}

	return false
}

func binaryTreeMinDepth(root *Node) int {
	result := 0

	if root == nil {
		return result
	}

	var q NodeQueue
	q.Enqueue(*root)

	for len(q) > 0 {
		size := len(q)

		for i := 0; i < size; i++ {
			current := q.Dequeue()

			if isLeafNode(current) {
				return result
			}

			if current.left != nil {
				q.Enqueue(*current.left)
			}
			if current.right != nil {
				q.Enqueue(*current.right)
			}
		}

		result++
	}

	return result
}
6

Could you at least better explain the output of the problem?
I want to try it myself without looking at the solution, but there’s barely anything…

7

Did you look at the picture? They want us to look for the smallest depth of a branch of the tree. If you been following in order you should have seen a tree section where it explains all the definition.

8

Is the final return depth needed? The early return should catch all cases right?

9 
def binary_tree_min_depth(root: Node) -> int:
    if not root:
        return 0
    
    level = 0
    queue = deque([root])

    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            if not all([node.left, node.right]):
                return level      
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            level += 1

    return level
10

Simpler Javascript Solution

function binaryTreeMinDepth(root) {
   if(!root) return 0;
   
   const q = [root];
   let level = -1;
    
   while(q.length){
       const numNodes = q.length;
       level = level + 1;
       
       for(let i = 0; i < numNodes; i++){
           const node = q.shift();
           
           if(!node.left && !node.right) return level;
           
           if(node.left) q.push(node.left);
           
           if(node.right) q.push(node.right);
       }
   }
   return level;
}
11

Needs more test cases, my incorrect solution passed, my mistake was checking that any child is None, not the both of them (the definition of a leaf)