Minimum 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.

Solution

Typical Recursive Solution

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
    }
}

Analysis

A very general recursive way to find number of nodes in a depth
The only tricky part can be the last line
If either left or right is 0, we return the opposite depth + 1 which is left + right + 1
This is because we must count nodes from root to leaf, cannot consider null leaf as real leaf

results matching ""

    No results matching ""