CareerCup

Asymptotically they will be the same though BFS can be written to stop as soon as a leaf node is found in which case it will not explore any nodes that are at a level below the leaf node with min depth.
which even in the worst case will explore half the nodes less... (since a tree with n nodes has atleast n/2 nodes as leaves and BFS can stop at the first leaf itself)
whereas you cannot say anything about the performance of a DFS since the leaf with min depth may be explored at the very end.

I think I am wrong regarding the n/2 nodes since that is only the case for a complete binary tree.
However I am atleast sure about this, the BFS approach will be better than the DFS approach, since BFS need not explore the entire tree in most cases whereas DFS will have to explore the entire tree in any case...

I would support BFS. Thats because BFS will stop as soon as it sees a node at a level with no children. But DFS would anyway have to traverse until every leaf node and then find which is the smallest path to a leaf node.
Comparing the complexities depends on the way the tree is constructed. So either might win. But on an average, BFS would win.

Here is the recursive implementation.

int min=Integer.MAX_VALUE;
void findMinDeapth(node root,int depth)
{
	if(root==null)
	{
		if(depth<min)
			min=depth;
		return;
	}
	findMinDeapth(root.left,depth+1);
	findMinDeapth(root.right,depth+1);
}

But i think BFS will be more efficient .

Here is the BFS approach

int findMinDeapth(node root)
{
	Queue<root> q1=new LinkedList<node>();
	Queue<root> q2=new LinkedList<node>();
	q1.add(root);
	int depth=0;
	while(!q1.isEmpty() || !q2.isEmpty())
	{		
		while(!q1.isEmpty())
		{
			node n=q1.remove();
			if(n.left == null && n.right == null)
				return depth;
			q2.add(n.left);
			q2.add(n.right);
		}
		depth++;
		while(!q2.isEmpty())
		{
			node n=q2.remove();
			if(n.left == null && n.right == null)
				return depth;			
			q1.add(n.left);
			q1.add(n.right);
		}
		
	}
}

They are essentially the same complexity-wise. Recursive approach implicitly does DFS building a stack, and the other builds queue.

int depthWithRec(Node * node)
{
if(node == null)
return null;
else
return min(depth(node->left), depth(node->right) + 1);
}

int depthWithoutRec(Node * node){
if(node != null) {
int lDepth = 0, rDepth = 0;
queue.enqueue(node);
while(queue()! = empty()) {
node = dequeue();

if(node->left != null) {
lDepth++;
queue.enqueue(node);

}
if(node->right!= null) {
rDepth++;
queue.enqueue(node);
}
return(min(lDepth,rDepth) +1);
}
}
else
return 0;
}

int mindepth(struct node* root)
     {
           if(root == NULL)
              return 0;
          else
          {
                int lefttreedepth = mindepth(root->left);
                int righttreedepth = mindepth(root->right);
                if(lefttreedepth<righttreedepth)
                     return lefttreedepth+1;
               else 
                      return righttreedepth+1;
          }
}

Depth(Node node)
{
  if(node == null) return 0;
  else return 1 + min(Depth(node->left),Depth(node->right));

}

Since it will traverse all the nodes I think complexity is O(n), but if you follow a dfs or an iterative approch complexity will be reduced, correct me if I am wrong

How about BFS counting the number of nodes in each layer interatively, until find the layer in depth d has nodes fewer than 2^(d-1)

//Recursive is better
public int minDepth(Node root)
{
if (root == null) { return 0; }
return 1 + Math.Min(minDepth(root.leftNode), minDepth(root.rightNode));
}