Function to find the minimum depth of a tree

Question

For a leetcode problem to find the minimum depth of the binary tree, I have written the below solutions. The solution is accepted, but can I do any other changes to make the code elegent?

 public class Solution {
 public int minDepth(TreeNode root) {
 if(root == null)
 {
 return 0;
 }
 //to handle the leaf node case...
 if(root.left == null && root.right == null)
 {
 return 1;
 }
 //To handle the case that has only right children..
 if(root.left == null)
 {
 return minDepth(root.right) + 1;
 }
 if(root.right == null)
 {
 return minDepth(root.left) + 1;
 }
 return Math.min( minDepth(root.left)+1,minDepth(root.right)+1);
 }
 }

• Jaime: Your 2nd, 3rd and 4th ifs are unnecessary, if you remove them the function will work just the same.
• abuzittin gillifirca: @Jaime You should post your comment as an answer.
• Jaime: I know, but it's hard to format code on a phone, maybe later today...

Answer 1

This code will visit every node in the tree, but it's not always necessary to do all that work. Instead you can do a breadth-first traversal of the tree, and look for the first node that has no children.

Consider this tree:

 o
 / \
 o o
 \
 o
 \
 o
 ...
 o
 \
 o

With a breadth-first traversal, you only need to look at two nodes to determine the minimum depth. With the current code, you will visit every node and use \$O(n)\$ stack space in the process.

In some cases you will have to traverse every node, but my point is that sometimes you can do better.

The only trick is that you also have to keep track of the depth of each node.

The idea is to:

• Enqueue the root onto a queue

• While the queue is not empty:

  • Dequeue from the queue
  • If the node has no children, return its depth; this is a node of minimum depth in the tree.
  • Otherwise, enqueue the children of the node onto the queue

• abuzittin gillifirca: Breadth first has the same time complexity (since you need to visit every node at least once either way), and worse space complexity O(n) vs O(log n) (average, assuming every branch has a some probability p of being non-null).
• mjolka: @abuzittingillifirca I've tried to address your comments in the latest edit.
• abuzittin gillifirca: Ok I now understand what you are trying to achieve. As I said I'm assuming test cases are not specifically stacked with degenerate cases. And if you think test cases are chosen otherwise you can still achieve the similar worst case time performance to breadth-first search using depth-first search with iterative deepening. Which should be the go-to algorithm if you do not have access to the actual test cases, but OPs simple depth first algorithm was apparently already enough.

Answer 2

There is no need to special-case anything but a null root:

 int minDepth(TreeNode root)
 {
 if (root == null) {
 return 0;
 }
 return 1 + Math.min(minDepth(root.left), minDepth(root.right));
 }

All the rest is automatically taken care of.