DFS (Depth First Search)

Introduction

➡️ Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
➡️ One starts at the root (selecting some arbitrary node as the root for a graph) and explore as far as possible along each branch before backtracking.

Implementation of DFS

➡️ Both the below implementations are same.
➡️ The only difference is, the first one uses Stack which you can visualize better
and for the second case, how the internal stack is used.
➡️ Both are the In-order Traversal of a Binary Tree.

Using Stack

public class Solution{
    public void dfs(Node root){
        Stack<Node> stack = new Stack<>();
        Node current = root;
        while(current != null || !stack.isEmpty()){
            if(current != null){
                stack.push(current);
                current = current.left;
            }else{
                current = stack.pop();
                System.out.println(current.data);
                current = current.right;
            }
        }
    }
}

Using Recursion

public class Solution{
    public void dfs(Node root){
        if(root == null) return;
        dfs(root.left);
        System.out.println(root.data);
        dfs(root.right);
        
    }
}

Common Problems (Frequently Asked Questions)

Binary Tree Paths

class Solution {    public List<String> binaryTreePaths(TreeNode root) {        List<List<Integer>> paths = new ArrayList<List<Integer>>();        // Edge case        if (root == null) {            return new ArrayList<String>();        }        List<Integer> path = new ArrayList<>();        dfsMethod1(root, path, paths);        // or        //dfsMethod2(root, path, paths);        System.out.println(paths);        return new ArrayList<String>();    }    private void dfsMethod1(TreeNode node,List<Integer> path,List<List<Integer>> paths) {        if (node == null) return;        path.add(node.val);        if (node.left == null && node.right == null) {            paths.add(new ArrayList<>(path));        }        dfs(node.left, path, paths);        dfs(node.right, path, paths);        path.remove(path.size() - 1);    }    //Alternative : You don't need to check the initial null condition, If all the recursive call    //are made only when the node's left and right is not null.    private void dfsMethod2(TreeNode node,List<Integer> path,List<List<Integer>> paths) {        path.add(node.val);        if (node.left == null && node.right == null) {            paths.add(new ArrayList<>(path));        }        if (node.left != null) {            dfs(node.left, path, paths);        }        if (node.right != null) {            dfs(node.right, path, paths);        }        path.remove(path.size() - 1);    }}

Path Sum

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

class Solution {    boolean flag = false;    public boolean hasPathSum(TreeNode root, int targetSum) {        if(root == null ) return false;        if(targetSum-root.val == 0 && root.left == null && root.right == null) return true;        return helper(root.left, targetSum-root.val) || helper(root.right, targetSum-root.val);            }    public boolean helper(TreeNode root, int sum){        if(root == null) return false;        if(sum-root.val == 0 && root.left == null && root.right == null) return true;        return helper(root.left, sum-root.val) || helper(root.right, sum-root.val);    }}

Same Tree

Input: p = [1,2,3], q = [1,2,3]
Output: true

Input: p = [1,2], q = [1,null,2]
Output: false

class Solution {    public boolean isSameTree(TreeNode p, TreeNode q) {        if(p == null && q == null) return true;        if(p == null && q != null || (p != null && q == null)) return false;                if(p.val == q.val) return true;        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);    }}