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

We use two methods to solve this problem. In the first approach, we use Breadth-First-Search, just as the level-order traversal, to find the minimum depth of a leaf node.

Java

01 public int minDepth(TreeNode root) {

02   if(root==null)

03     return 0;

04   LinkedList<TreeNode> trees=new LinkedList<TreeNode>();

05   LinkedList<Integer> depth=new LinkedList<Integer>();

06   int level=1;

07   trees.add(root);

08   depth.add(level);

09   TreeNode top=null;

10   int curr_depth=0;

11   while(trees.size()>0)

12   {

13     top=trees.remove();

14     curr_depth=depth.remove();

15     if(top.left==null && top.right==null)

16     {

17       return curr_depth;

18     }

19     if(top.left!=null)

20     {

21       trees.add(top.left);

22       depth.add(curr_depth+1);

23     }

24     if(top.right!=null)

25     {

26       trees.add(top.right);

27       depth.add(curr_depth+1);

28     }

29   }

30   return curr_depth;

31 }

In the second approach, we use a recursive algorithm to find the minimum depth, which is relatively easier.

Java

01 public int minDepth(TreeNode root) {
02   if(root==null)
03     return 0;
04   if(root.left==null)
05   {
06     return minDepth(root.right)+1;
07   }
08   if(root.right==null)
09   {
10     return minDepth(root.left)+1;
11   }
12   return findMin(minDepth(root.left),minDepth(root.right))+1;
13 }
14 public int findMin(int a, int b)
15 {
16   return a<b?a:b;
17 }