12. Minimum depth in a binary tree

111. Minimum Depth of Binary TreeEasy5.8K1.1KCompanies

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 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

• The number of nodes in the tree is in the range [0, 105].

• -1000 <= Node.val <= 1000

Minimum Depth of Binary Tree - LeetCodeLeetCode

DFS

Time: O(V)

Space: O(H), recursion stack

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

// DFS
var minDepth = function(root) {
    if (root === null) return 0;
    if (root.left === null && root.right === null) return 1;

    return findMinDepth(root, 1);
};

function findMinDepth(node, step = 1) {
    if (node === null) {
        return 0;
    }

    if (node.left === null && node.right === null) {
        return step;
    }

    const left = findMinDepth(node.left, step + 1);
    const right = findMinDepth(node.right, step + 1);
    // console.log(left, right);

    if (left === 0) return right;
    if (right === 0) return left;
    return Math.min(left, right);
}

BFS

Time: O(V), height of tree

Space: O(v), v is num of nodes

// BFS
var minDepth = function(root) {
    if (root === null) return 0;
    if (root.left === null && root.right === null) return 1;

    const q = [[root, 1]];

    while (q.length > 0) {
        const [node, step] = q.shift();
        
        if (node.left === null && node.right === null) {
            return step;
        }
        
        if (node.left !== null) {
            q.push([node.left, step + 1]);
        }
        
        if (node.right !== null) {
            q.push([node.right, step + 1]);
        }
    }

    return 0;
};