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);
        }
    }

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

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.