My solution to minimum depth of binary tree

• `````` int minDepth(TreeNode *root) {
if (root == NULL)
{
return 0;
}

int left = minDepth(root->left);
int right = minDepth(root->right);

if (left == 0 && right == 0) // leaf
{
return 1;
} else if (left == 0)
{
return 1 + right;
} else  if (right == 0)
{
return 1 + left;
} else
{
return 1 + min(left, right);
}
}
``````

My solution is O(n) in time and O(1) in space. This is done using pre-order traversal, where we recurse through the whole tree and then determine what the minimum depth would be.

Can we do any better?

• Yes.Time Complexity in the average case can be reduced by pruning the tree when required. The following code shows it.

``````class Solution {
private:
int min_depth = 10000;
public:
void minHelper(TreeNode *root, int depth)
{
if(depth >= (min_depth))
return;
if(root->left == NULL && root->right==NULL)
{
min_depth = depth+1;
return;
}
if(root->left)
minHelper(root->left, depth+1);
if(root->right)
minHelper(root->right, depth+1);
}

int minDepth(TreeNode *root) {
if(root == NULL)
return 0;
minHelper(root, 0);
return min_depth;
}
};
``````

• There is no O(1) space solution with recursion.

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