# Iterative deepening DFS Java solution. Better than both BFS and DFS.

• time complexity is as good as BFS. space complexity is as good as DFS. Could you give me some suggestion on my code?Thanks!

public class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
return iterativeDeepeningDFS(root);
}
private boolean depthLimitedSearch(TreeNode root,int depth){
boolean left = false;
boolean right = false;
if(depth>0){
if(root.left==null&&root.right==null){
return true;
}
if(root.left!=null) {
left = depthLimitedSearch(root.left, depth-1);
}
if(root.right!=null) {
right = depthLimitedSearch(root.right, depth-1);
}
return left||right;
} else {
return false;
}
}
private int iterativeDeepeningDFS(TreeNode root){
int thisDepth = 1;
boolean foundMin = false;
while(true){
foundMin = depthLimitedSearch(root,thisDepth);
if(foundMin){
return thisDepth;
} else {
thisDepth++;
}
}
}

}

• Cool solution. However, I still think BFS is faster due to the fact that you will revisit many nodes each time you increase the depth.

• Yes, you are right. However, when N is big enough, we can ignore those extra visited node.
For a tree with b=10 and d=5
BFS=10+100+1,000+10,000+100,000=111,110
IDS=50+400+3,000+20,000+100,000=123,450
Iterative deepening is the preferred uninformed search method when there is a large search space and the depth of the solution is not known.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.