Min depth of a binary tree using BFT?

Question

I'm trying to figure out the minimum depth to a leaf node using breadth first search. I have the following basic structure

public int BFS(Node root){
    if (root == null) return 0;
    Queue<Node> q = new LinkedList<Node>();
    int min = 1;
    q.clear(); // I saw this in a queue example, unsure if needed
    q.add(root);
    while (! q.isEmpty()){
        Node n = q.remove();
        if (n.left != null) q.add(n.left);
        if (n.right != null) q.add(n.right);
    }
 }

I'm not sure where to update the min height counter. I had thought about placing it inside the if statements as temp loop variables l & r where I would set them to 1 if the left or right is not null, 0 else. Then add the min of these 2 to the min height but this only works if I'm at one level above the leafs.

Answer 1

The idea should be something like:

• First node added to the queue should have distance = 1.
• For new nodes added to the queue: distance = actual node distance + 1
• When you find a leaf, you return actual node distance. END.

In pseudocode:

root.depth := 1
q := create queue
q.add(root)

while q is not empty
    Node n := q.dequeue()

    if (n is leaf) then
       return n.depth

    if (n.left is not null)  then
       n.left.depth := n.depth + 1
       q.add(n.left)
    if (n.right is not null) then
       n.right.depth := n.depth + 1
       q.add(n.right)

return 0

Answer 2

You could use a queue of pairs (node, depth). Since the search is BFT, the first leaf contains the minimum depth.

Based on your code, the algorithm would be something like that (pseudo java code):

public int BFS(Node root)
{
    if (root == null) 
    return 0;

    Queue<Pair<Node,int>> q = new LinkedList<Pair<Node,int>>();
    q.add(new Pair(root, 0));

    while (! q.isEmpty()) {

        Pair p = q.remove();
        Node n = p.getFirst();

        if (n.left == null && n.right == null) // is this a leaf?
            return p.getSecond(); // yes! ==> p.getSecond() is its min depth

        if (n.left != null) 
            q.add(new Pair(n.left, p.getSecond() + 1));
        if (n.right != null) 
            q.add(new Pair(n.right, p.getSecond() + 1));
    }
}

Of course, you need the Pair class, but I leave to you these details