LexisNexis Interview Question
Software Engineer / DevelopersAlgorithm:
If node is null, return 0.
Else find min of the minimum depth for left node and right node + 1.
int minDepth(TreeNode n)
{
if ( n == null )
return 0;
return Math.min( minDepth(n.left), minDepth(n.right) ) + 1;
This will not work. It will return 2 for the example given. Try it yourself.
This could work
int MinDepth(TreeNode *node)
{
if( node == 0 )
{
return 0;
}
int hL = MinDepth(node->left);
int hR = MinDepth(node->right);
if( (hL == 0) || (hR == 0) )
{
return max( hL, hR ) + 1;
}
return min( hL, hR ) + 1;
}
@riderchap. Excellent! I've seen wrong implementations of this problem many times. A small fix: subtract 1 from the final result. Also, there is no need to traverse the whole tree to find out the minDepth. You can traverse the tree level by level. The level where you find the first leaf is your minDepth.
Breadth First Search
- Synonymous November 20, 2010