# LeetCode 111. Minimum Depth of Binary Tree

### Kaitian Xie twitter logo github logo Apr 16・1 min read

LeetCode in Java (8 Part Series)

``````public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

Queue<TreeNode> q = new LinkedList<>();
TreeNode rightMost = root;
int depth = 1;
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node.left == null && node.right == null) {
break;
}
if (node.left != null) {
}
if (node.right != null) {
}
if (node == rightMost) {
depth++;
rightMost = (node.right != null) ? node.right : node.left;
}
}

return depth;
}
}
``````

We use BFS to solve this problem. We add nodes at the same level to a queue `q`. We iterate through each of the nodes. When we encounter a leaf node, we stop and return `depth` (the minimum depth). After iterating all the nodes at the same level, we still cannot find a leaf node, we increment `depth` by 1 then repeat the above process for the nodes at the next level. We can use DFS as well. However, BFS outperforms DFS on highly unbalanced trees since it terminates once it reaches the first leaf node.

Time Complexity: `O(n)`

Extra Space: `O(1)`

LeetCode in Java (8 Part Series)

DISCUSS Sore eyes?

dev.to now has dark mode.

Go to the "misc" section of your settings and select night theme ❤️

Classic DEV Post from Mar 19

## Jack of the Stack  