# My solution used level-order traversal

• level-order traversal and record current level depth, when meet a node which both child is null then return, no need to go farther

``````public class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
int depth = 1;
TreeNode temp,magic = new TreeNode(0);
while(!queue.isEmpty()){
temp = queue.poll();
if(temp.equals(magic)){
if(!queue.isEmpty()){
depth++;
}
continue;
}
if(temp.left == null && temp.right == null)
return depth;
if(temp.left != null)
if(temp.right != null)
}
return depth;
}
}
``````

Any better solution?

• Don't forget deleted those memories.

• I using recursion for solve this problem:

`````` int minDepth(TreeNode *root) {
if (NULL == root) return 0;
if (NULL == root->left && NULL == root->right) {
return 1;
}

int minDepthTree = INT_MAX;
if (NULL != root->left) {
minDepthTree = min(minDepthTree, minDepth(root->left) + 1);
}
if (NULL != root->right) {
minDepthTree = min(minDepthTree, minDepth(root->right) + 1);
}

return minDepthTree;
}``````

• I think your solution is better than other recursive solutions using DFS-like method. There's no need to traverse all the nodes to get the min depth of a tree using BFS-like method.

• I used two queues to avoid the confusing magic element.

``````public class Solution {
public int minDepth(TreeNode root) {
if(root == null)
return 0;
//is an empty tree
if(root.left == null && root.right == null)
return 1;

nQ.offer(root);
dQ.offer(1);

while(!nQ.isEmpty()){
TreeNode curNode = nQ.poll();
int curDepth = dQ.poll();

if(curNode.left == null && curNode.right == null)
return curDepth;
if(curNode.left != null){
nQ.offer(curNode.left);
dQ.offer(curDepth+1);
}
if(curNode.right != null){
nQ.offer(curNode.right);
dQ.offer(curDepth+1);
}
}

return -1;
}}
``````

• my solution using recursion in JAVA:

`````` public int minDepth(TreeNode root) {
if(root == null)
return 0;
int left=minDepth(root.left);
int right=minDepth(root.right);
if(left==0)
return right+1;
if(right==0)
return left+1;
return left<right ? left+1:right+1;
}``````

• ``````class Solution {
public:
int minDepth(TreeNode *root) {
if (root == NULL) return 0;
/*
if (root->left == NULL && root->right == NULL) return 1;
if (root->left == NULL) return 1+minDepth(root->right);
if (root->right == NULL) return 1+minDepth(root->left);
return 1 + min(minDepth(root->left), minDepth(root->right));
*/
queue<TreeNode *> q;
q.push(root);
int cur = 1;
int nxt = 0;
int height = 1;
while (!q.empty()) {
TreeNode *top = q.front();
q.pop();
--cur;
if (top->left == NULL && top->right == NULL) return height;
if (top->left != NULL) { q.push(top->left); ++nxt; }
if (top->right != NULL) { q.push(top->right); ++nxt; }
if (cur == 0) {
cur = nxt;
nxt = 0;
++height;
}

}
}
};``````

• This version of solution in Java includes two queues which are implemented as linked lists, for better readability. Time complexity is O(n) and Space Complexity is O(n)

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

while(!nodes.isEmpty()){
TreeNode curr = nodes.remove();
int count = counts.remove();

if(curr.left != null){
}

if(curr.right != null){
}

if(curr.left == null && curr.right == null){
return count;
}
}

return 0;
}
}``````

• My Java code with a BFS method. Besides the queue, only two variables are used.

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

TreeNode endOfLevel = root;
int depth = 1;

while( !queue.isEmpty() ) {
TreeNode node = queue.remove();
if(node.left==null && node.right==null) return depth;
if(node == endOfLevel) {
endOfLevel = node.right==null ? node.left : node.right;
depth++;
}
}

return depth;
}``````

• how to understand return left<right ? left+1:right+1; why we need to add 1 for left or right min path?

• because it indicates there is another level underneath current node, and the add 1 is to take the next level into account.

• probably a easier level order using the size of queue to determine the depth

``````public int minDepth(TreeNode root) {
if (root == null){
return 0;
}
int depth = 1;
while (!queue.isEmpty()){
int size = queue.size(); // determine the loop size
for (int i = 0; i< size; i++){
TreeNode node = queue.poll();
if (node.left == null && node.right == null){
return depth;
}
if (node.left!=null){
}
if (node.right!=null){
}
}
depth ++;
}
return depth;
}``````

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

int minDepth = 0;
TreeNode t = root;
TreeNodeLevel rootLevel = new TreeNodeLevel(root,1);
queue.offer(rootLevel);
while(queue.size() > 0)
{
TreeNodeLevel r = queue.poll();

if(r.node.left == null&&r.node.right == null)
return r.level;
else
{
if(r.node.left != null)
{
TreeNodeLevel rl = new TreeNodeLevel(r.node.left,r.level + 1);
queue.offer(rl);
}
if(r.node.right != null)
{
TreeNodeLevel rr = new TreeNodeLevel(r.node.right,r.level + 1);
queue.offer(rr);
}
}
}
return Integer.MAX_VALUE;
}
class TreeNodeLevel
{
TreeNode node;
int level;
public TreeNodeLevel(TreeNode node,int level)
{
this.node = node;
this.level = level;
}
}
``````

}

• A Python Code

``````class Solution:
# @param root, a tree node
# @return an integer
# Use BFS so that no need for recursion and faster trimming.
def minDepth(self, root):
if root==None:
return 0

stack=[(root,1)]
while len(stack)!=0:
node=stack.pop(0)
if node[0]==None:
continue
if node[0].left==None and node[0].right==None:
return node[1]
else:
stack.append((node[0].left,node[1]+1))
stack.append((node[0].right,node[1]+1))

return 0
``````

• My java solution without recursion:

``````public class Solution {
public int minDepth(TreeNode root) {

if (root == null) {
return 0;
}
TreeNode node = root;

int cur = 0;
int order = 1;
int next = 0;
int level = 1;

queue.offer(node);

while (!queue.isEmpty()) {
node = queue.poll();
cur++;

if (node.left == null && node.right == null) {
return level;
}

if (node.left != null) {
next++;
queue.offer(node.left);
}
if (node.right != null) {
next++;
queue.offer(node.right);
}
if (cur == order) {
level++;
order = next;
next = 0;
cur = 0;
}
}
return level;
}``````

• if you solution is not BFS for this problem, then yours is not an ideal solution. BFS reaches the minimal depth leaf node before DFS.

• Is the time complexity of this just O(n) ? Or is that just in worst case

• nice iterative solution using queue!

• This post is deleted!

• class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL) return 0;
queue<TreeNode*> Queue;
int len= 1;
Queue.push(root);
while(!Queue.empty())
{
int size= Queue.size();
for(int i = 0;i<=size-1;i++)
{
TreeNode* p = Queue.front();
Queue.pop();
if(p->left != NULL)
{

``````                Queue.push(p->left);
}

if(p->right != NULL)
{

Queue.push(p->right);
}

if(p->left ==NULL  && p->right == NULL)
{
return len;
}
}
if(!Queue.empty())
{
len++;
}
}
return len;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.