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.

Solution: Recursion Top Down

When we reach a leaf node, we update our min depth.

void helper(TreeNode *root, int depth, int &minDepth) {
    if (!root) return;

    if (!root->left && !root->right) minDepth = min(minDepth, depth);
    if (root->left) helper(root->left, depth+1, minDepth);
    if (root->right) helper(root->right, depth+1, minDepth);
}

int minDepth(TreeNode* root) {
    if (!root) return 0;

    int minDepth = INT_MAX;
    helper(root, 1, minDepth);
    return minDepth;
}

Solution: Using Recursive

int minDepth(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    if (root->left && !root->right) return 1 + minDepth(root->left);
    if (root->right && !root->left) return 1 + minDepth(root->right);

    return 1 + min(minDepth(root->left), minDepth(root->right));
}

Solution: Traverse Tree Using Level Order

int minDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode *> q;
    q.push(root);

    int depth = 0;
    while (true) {
        int count = q.size();
        if (count == 0) break;

        depth += 1;
        while (count > 0) {
            TreeNode *node = q.front();
            q.pop();
            count -= 1;

            if (!node->left && !node->right) return depth;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return depth;
}