Find minimum depth in a binary tree

Question

Description:

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.

Leetcode

Code:

class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; return recur(root, 1); } private int recur(TreeNode root, int depth) { if (root == null) return 0; if (root.left == null && root.right == null) { return depth; } int ldepth = recur(root.left, depth + 1); int rdepth = recur(root.right, depth + 1); // either left or right subtree was not a leaf node // ignore non leaf node. if (ldepth == 0 || rdepth == 0) { return Math.max(ldepth, rdepth); } else { return Math.min(ldepth, rdepth); } } } 

Question:

I need to know if the given logic can be simplified?

Answer 1

If by simplification you mean optimization, then only one thing came to my mind:

• Whenever you find a leaf node, remember its depth in minmalFound variable.

• When again you hit the next leaf node you compare its depth with previously remembered node. And save the minimum of both into minmalFound.

And the main logic to add is whenever you are searching a certain path and find out that the depth becomes as great as the existing minmalFound, then you stop searching that path.

Here is code to demonstrate this technique:

public class Solution { public static int minDepth(TreeNode root) { reccallscount = 0; minmalFound = -1; if (root == null) return 0; return recur(root, 1); } public static boolean doFaster = false; private static int minmalFound = -1; private static int reccallscount = 0; private static int recur(TreeNode root, int depth) { reccallscount++; if (root == null) return 0; if (root.left == null && root.right == null) { if (minmalFound == -1) { minmalFound = depth; } else { minmalFound = Math.min(minmalFound, depth); } return depth; } if (doFaster) { if (minmalFound != -1 && depth + 1 >= minmalFound) { return minmalFound * 2; } } int ldepth = recur(root.left, depth + 1); int rdepth = recur(root.right, depth + 1); // either left or right subtree was not a leaf node // ignore non leaf node. if (ldepth == 0 || rdepth == 0) { if (ldepth != 0) { minmalFound = Math.min(minmalFound, ldepth); } else if (rdepth != 0) { minmalFound = Math.min(minmalFound, rdepth); } return Math.max(ldepth, rdepth); } else { int value = Math.min(ldepth, rdepth); minmalFound = Math.min(minmalFound, value); return value; } } public static void main(String args[]) { TreeNode root = new TreeNode(); root.left = new TreeNode(); root.left.right = new TreeNode(); root.right = new TreeNode(); root.right.left = new TreeNode(); root.right.left.right = new TreeNode(); root.right.left.right.left = new TreeNode(); Solution.doFaster = false; int min = minDepth(root); System.out.println("Minimum " + min + " found with " + reccallscount + " recursive calls"); Solution.doFaster = true; min = minDepth(root); System.out.println("Minimum " + min + " found with " + reccallscount + " recursive calls with faster approach"); } } class TreeNode { TreeNode left = null; TreeNode right = null; } 

In the code above, I created a tree with left side depth = 3 and right side depth = 5. I ran minDepth() twice; first using your algorithm, and again with my addition. The result is then printed:

Minimum 3 found with 11 recursive calls Minimum 3 found with 5 recursive calls with faster approach