trjhtr

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) 

Question:

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

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) 

 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