Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

C++:
01 /**
02  * Definition for binary tree
03  * struct TreeNode {
04  *     int val;
05  *     TreeNode *left;
06  *     TreeNode *right;
07  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
08  * };
09  */
10  void minDepthHelper(TreeNode* root, int& min, int current)
11  {
12      if(root==NULL)
13      {
14          return;
15      }
16      if((root->left==NULL)&&(root->right==NULL))
17      {
18          if((min==-1)||(current+1<min))
19             min=current+1;
20      }
21      if((min==-1)||(current+1<min))
22      {
23          minDepthHelper(root->left,min,current+1);
24          minDepthHelper(root->right,min,current+1);
25      }
26  }
27 class Solution {
28 public:
29     int minDepth(TreeNode *root) {
30         // Start typing your C/C++ solution below
31         // DO NOT write int main() function
32         if(root==NULL)
33             return 0;
34         int result=-1;
35         minDepthHelper(root,result,0);
36         return result;
37     }
38 };
Advertisements
This entry was posted in Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s