## DEV Community is a community of 887,564 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Kaitian Xie

Posted on • Updated on

# LeetCode 111. Minimum Depth of Binary Tree

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

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)`