Min Depth of Binary Tree

Problem

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

Attempt

We can traverse tree and record the min depth among leaf nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int min_depth = INT_MAX;
    void traverse(TreeNode *root, int current_depth) {
      if (root == nullptr) {
        min_depth = min(min_depth, current_depth - 1);
        return;
      }
      traverse(root->left, current_depth + 1);
      traverse(root->right, current_depth + 1);
    }
public:
    int minDepth(TreeNode* root) {
      traverse(root, 1);
      return min_depth;
    }
};

Aha! I need to read the question more carefully 😧 I need to count the number of nodes!!! Additionally, we need to exclude the paths where a leaf may be missing, since that would skew the result! This is a pretty good problem, even though it’s marked as easy. I also don’t need to add a separate recursive function. We can just use the given function recursively.

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
      if (!root) return 0;
      int L = minDepth(root->left);
      int R = minDepth(root->right);
      // if one of them is zero then we need to return the non-zero value
      return ( 1 + ((L && R)? min(L, R) : max(L, R)));
    }
};