c++ - Cracking the coding interview. 4.1 Min Depth formula -

in ctci, there give formula minimum depth binary tree , confused it. here code:

    public static int mindepth(treenode root) {         if (root == null) {            return 0;         }         return 1 + math.min(mindepth(root.left), mindepth(root.right));     } 

the definition of minimum depth leaf node shortest path root correct? if definition wrong please correct me.

dilemma: made bst root 15. proceeded add 5, 7, 10, 20, 25, 30, 35 tree. using code output the min 2. if have added 10 , 25, output min 2. suppose correct?

i translated code c++ here please tell me if made mistake in code mess up

     int findmin(node* root)      {          if (root == null)             return 0;           return 1 + std::min(findmin(root->left), findmin(root->right));      }      void addnum(node*& root, int n)     {         if (root == null){             node* temp = new node(n);             root = temp;             return;         }           if (n > root->num){              addnum(root->right, n);          }          else{              addnum(root->left, n);          }      } 

thanks much!

for input {15, 10, 20}

input 1: initially, add 15 bst

    15 

input 2: now, add 10 bst

    15    /   10 

input 3: now, add 20 bst

    15    /  \   10  20 

therefore, min , max height of bst 2

now, consider input case {15, 5, 7, 10, 20, 25, 30, 35}

input 1: initially, add 15 bst

    15 

input 2: now, add 5 bst

    15    /   5 

input 3: now, add 7 bst

    15    /   5    \     7 

input 4: now, add 10 bst

    15    /   5    \     7      \       10 

input 5: now, add 20 bst

    15    /  \   5   20     \     7      \       10 

input 6: now, add 25 bst

    15    /  \   5   20     \    \     7   25      \       10 

input 7: now, add 30 bst

    15    /  \   5   20     \    \     7   25      \    \       10   30 

input 8: now, add 35 bst

    15    /  \   5   20     \    \     7   25      \    \       10   30             \             35 

as see above diagram min height of bst = 4 & max height = 5

therefore, if findmin code, find bug:

int findmin(node* root)  {      if (root == null)         return 0;       return 1 + std::min(findmin(root->left), findmin(root->right));  }  

bug : when root pointing 5 (i.e left child of 15 in second example) return 1 parent. ( why ?)

correction : below code snippet work :

int min_depth(struct node* root, int depth) {     if (root->left == null && root->right == null)         return depth;      int x = (root->left != null) ? min_depth(root->left, depth+1) :  depth;     int y = (root->right != null) ? min_depth(root->right, depth+1) : depth;      return (x < y) ? x : y; }