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


  • 0
    E

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

    }


  • 0
    K

    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.


  • 0
    E

    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.


Log in to reply
 

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