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]`

,

3 / \ 9 20 / \ 15 7

return its minimum depth = 2.

## Solution

**DFS Approach**

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { 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 1 + Math.Max(left,right); else return 1 + Math.Min(left,right); } }

**BFS Approach**

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public int MinDepth(TreeNode root) { Queue<TreeNode> q = new Queue<TreeNode>(); if(root == null) return 0; q.Enqueue(root); int level = 1; while(q.Count > 0){ int size = q.Count; while(size > 0) { TreeNode node = q.Dequeue(); if(node.left == null && node.right == null){ return level; } if(node.left != null) q.Enqueue(node.left); if(node.right != null) q.Enqueue(node.right); size--; } level++; } return level; } }

In both the approaches, time complexity and space complexity is O(n).