How to find the minimum depth of a binary tree

The minimum depth of a binary tree is the number of nodes from the root node to the nearest leaf node.

Let's see an example.  

 

What is the minimum depth of the binary tree? Based on the definition: is the number of nodes from the root node to the nearest leaf node. The tree has only one the shortest path:

• 1 -> 2

The minimum depth of the binary tree equals two.

 

Algorithm

To count the minimum depth we can use recursion:

• Recursively calculate the height of the binary tree to the left of the root
• Recursively calculate the height of the binary tree to the right of the root
• Take the minimum value from the heights of the left and right subtrees and add one, to account the root node

 

Code

    public int MinDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = MinDepth(root.Left);
        int right = MinDepth(root.Right);

        if (left == 0 || right == 0)
        {
            return left + right + 1;
        }

        return Math.Min(left, right) + 1;
    }

Time Complexity: O(n)