Aug 28, 2025

Depth-First Search

Overview

Depth-first search follows one branch as far as possible before returning to the previous decision point. Recursion stores the unfinished traversal and local state on the call stack.

On a binary tree, the left and right references define the neighbors. A valid tree has no cycles, so DFS normally needs only a null-node base case. State such as a path sum or allowed value range can be passed downward, while values such as subtree height are returned upward. Visiting every node takes O(n) time and up to O(h) call-stack space.

On an adjacency-list graph, each node may have many neighbors, shared paths, and cycles. Add a node to seen before visiting its neighbors. A complete traversal takes O(V + E) time.

A matrix is an implicit graph whose cells are nodes and whose neighbors are usually the four adjacent coordinates. Check bounds and the cell condition before processing, then mark the cell before recursing. Marking can use a separate visited structure or an in-place value change; restore the value only when the algorithm requires backtracking.

Templates

Binary tree

Return a base value when node is null.
Recursively process node.left and node.right.
Combine their results with the current node while recursion unwinds.

class BinaryTreeDfsTemplate {
	public int dfs(TreeNode node) {
		if (node == null) {
			return 0;
		}

		int left = dfs(node.left);
		int right = dfs(node.right);
		return 1 + Math.max(left, right);
	}
}

def dfs(node: "TreeNode | None") -> int:
    if not node:
        return 0

    left = dfs(node.left)
    right = dfs(node.right)
    return 1 + max(left, right)

Adjacency-list graph

Return when the node is already in seen.
Mark it before traversing its adjacency list.
Run DFS from additional starting nodes when the graph may be disconnected.

import java.util.List;

public class GraphDfsTemplate {
	public void dfs(int node, List<List<Integer>> adjList, boolean[] seen) {
		if (seen[node]) {
			return;
		}

		seen[node] = true;

		for (int nei : adjList.get(node)) {
			dfs(nei, adjList, seen);
		}
	}
}

def dfs(
    node: int,
    adj_list: list[list[int]],
    seen: set[int],
) -> None:
    if node in seen:
        return

    seen.add(node)

    for nei in adj_list[node]:
        dfs(nei, adj_list, seen)

Matrix

Reject out-of-bounds cells, visited cells, and cells that fail the required condition.
Mark the current cell before visiting its four neighbors.
Replace matrix[row][col] != 1 with the condition required by the problem.

class MatrixDfsTemplate {
	private int R;
	private int C;

	public boolean[][] traverse(int[][] matrix, int startRow, int startCol) {
		R = matrix.length;
		C = matrix[0].length;
		boolean[][] seen = new boolean[R][C];
		dfs(matrix, startRow, startCol, seen);
		return seen;
	}

	private void dfs(int[][] matrix, int row, int col, boolean[][] seen) {
		if (row < 0 || row >= R ||
			col < 0 || col >= C ||
			seen[row][col] ||
			matrix[row][col] != 1) {
			return;
		}

		seen[row][col] = true;
		dfs(matrix, row + 1, col, seen);
		dfs(matrix, row - 1, col, seen);
		dfs(matrix, row, col + 1, seen);
		dfs(matrix, row, col - 1, seen);
	}
}

def traverse(
    matrix: list[list[int]],
    start_row: int,
    start_col: int,
) -> list[list[bool]]:
    R, C = len(matrix), len(matrix[0])
    seen = [[False] * C for _ in range(R)]

    def dfs(row, col):
        if (
            row < 0
            or row >= R
            or col < 0
            or col >= C
            or seen[row][col]
            or matrix[row][col] != 1
        ):
            return

        seen[row][col] = True
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    dfs(start_row, start_col)
    return seen

Problems

104. Maximum Depth of Binary Tree

The depth of a null tree is zero. For every real node, recursively compute the depths of both subtrees and add one for the current node. Each node is visited once.

class Solution {
	public int maxDepth(TreeNode root) {
		return helper(root);
	}

	private int helper(TreeNode node) {
		if (node == null) {
			return 0;
		}

		return 1 + Math.max(
			helper(node.left),
			helper(node.right)
		);
	}
}

from typing import Optional

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def helper(node: Optional[TreeNode]):
            if not node:
                return 0

            return 1 + max(helper(node.left), helper(node.right))

        return helper(root)

112. Path Sum

Decide whether a root-to-leaf path equals a target sum. Accumulate psum as DFS descends, and return true when a leaf is reached with psum == targetSum.

class Solution {
	public boolean hasPathSum(TreeNode root, int targetSum) {
		return helper(root, 0, targetSum);
	}

	private boolean helper(TreeNode node, int psum, int targetSum) {
		if (node == null) {
			return false;
		}

		psum += node.val;
		if (node.left == null &&
			node.right == null &&
			psum == targetSum) {
			return true;
		}

		return helper(node.left, psum, targetSum) ||
			helper(node.right, psum, targetSum);
	}
}

from typing import Optional

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

        def helper(node, psum):
            if not node:
                return False

            psum += node.val
            if node.left is None and node.right is None and psum == targetSum:
                return True

            return helper(node.left, psum) or helper(node.right, psum)

        return helper(root, 0)

1448. Count Good Nodes in Binary Tree

A node is good when no earlier node on its root-to-node path has a greater value. Pass the maximum value seen on the current path into each recursive call. Count the node when its value reaches or exceeds that maximum, then update the maximum before visiting its children.

class Solution {
	private int res;

	public int goodNodes(TreeNode root) {
		res = 0;
		if (root == null) {
			return res;
		}

		dfs(root, root.val);
		return res;
	}

	private void dfs(TreeNode node, int currMax) {
		if (node == null) {
			return;
		}

		if (node.val >= currMax) {
			res++;
		}
		currMax = Math.max(node.val, currMax);
		dfs(node.left, currMax);
		dfs(node.right, currMax);
	}
}

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        self.res = 0
        if not root:
            return self.res

        def dfs(node, curr_max):
            if not node:
                return

            if node.val >= curr_max:
                self.res += 1
            curr_max = max(node.val, curr_max)
            dfs(node.left, curr_max)
            dfs(node.right, curr_max)

        dfs(root, root.val)
        return self.res

98. Validate Binary Search Tree

Pass the exclusive minimum and maximum values allowed at each node. The left subtree inherits the current minimum and uses the node’s value as its maximum; the right subtree uses the node’s value as its minimum and inherits the current maximum. Any value outside its allowed range invalidates the tree.

class Solution {
	public boolean isValidBST(TreeNode root) {
		return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}

	private boolean helper(TreeNode node, long allowedMin, long allowedMax) {
		if (node == null) {
			return true;
		}

		if (node.val <= allowedMin || node.val >= allowedMax) {
			return false;
		}

		boolean left = helper(node.left, allowedMin, node.val);

		boolean right = helper(node.right, node.val, allowedMax);

		return left && right;
	}
}

from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def helper(node, allowed_min, allowed_max):
            if not node:
                return True

            if node.val <= allowed_min or node.val >= allowed_max:
                return False

            left = helper(node.left, allowed_min, node.val)

            right = helper(node.right, node.val, allowed_max)

            return left and right

        return helper(root, float("-Inf"), float("Inf"))

113. Path Sum II

Track the current root-to-node path and its accumulated sum. Append the current value before visiting the children, copy the path when a leaf reaches targetSum, and pop the value before returning so the same path list can be reused by sibling branches.

import java.util.ArrayList;
import java.util.List;

class Solution {
	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> curr = new ArrayList<>();

		backTrack(root, 0, targetSum, curr, res);
		return res;
	}

	private void backTrack(TreeNode node, int psum, int targetSum, List<Integer> curr, List<List<Integer>> res) {
		if (node == null) {
			return;
		}

		psum += node.val;
		curr.add(node.val);
		if (psum == targetSum &&
			node.left == null &&
			node.right == null) {
			res.add(new ArrayList<>(curr));
		}

		backTrack(node.left, psum, targetSum, curr, res);
		backTrack(node.right, psum, targetSum, curr, res);
		curr.remove(curr.size() - 1);
	}
}

from typing import List, Optional

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        psum = 0
        curr = []

        def backTrack(node, psum):
            if not node:
                return

            psum += node.val
            curr.append(node.val)
            if psum == targetSum and node.left == None and node.right == None:
                res.append(curr.copy())

            backTrack(node.left, psum)
            backTrack(node.right, psum)
            curr.pop()

        backTrack(root, 0)
        return res

687. Longest Univalue Path

Use postorder DFS so both subtrees are always visited. Each call returns the longest same-value path extending downward from its node. Reset a child’s contribution to zero when its value differs, update the global result with left + right, and return the longer one-sided path to the parent.

class Solution {
	private int res;

	public int longestUnivaluePath(TreeNode root) {
		res = 0;
		helper(root);
		return res;
	}

	private int helper(TreeNode node) {
		if (node == null) {
			return 0;
		}

		// Must ALWAYS call helper on both children to traverse the entire tree
		int left = helper(node.left);
		int right = helper(node.right);

		// If values are not the same, there is no contribution from that child
		if (node.left == null || node.val != node.left.val) {
			left = 0;
		}
		if (node.right == null || node.val != node.right.val) {
			right = 0;
		}

		res = Math.max(res, left + right);
		return 1 + Math.max(left, right);
	}
}

from typing import Optional

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        self.res = 0

        def helper(node):
            if not node:
                return 0

            # Must ALWAYS call the helper on left and right children to traverse the entire tree
            left, right = helper(node.left), helper(node.right)
            # If values are not the same, no contribution from children
            if not node.left or node.val != node.left.val:
                left = 0
            if not node.right or node.val != node.right.val:
                right = 0
            self.res = max(self.res, left + right)
            return 1 + max(left, right)

        helper(root)
        return self.res

133. Clone Graph

Deep-copy a connected graph. Map each original node to its clone before visiting neighbors; that early insertion both preserves shared references and prevents infinite recursion around cycles.

import java.util.HashMap;
import java.util.Map;

class Solution {
	private final Map<Node, Node> nodeToCopy = new HashMap<>();

	public Node cloneGraph(Node node) {
		return dfs(node);
	}

	private Node dfs(Node node) {
		if (node == null) {
			return null;
		}

		if (nodeToCopy.containsKey(node)) {
			return nodeToCopy.get(node);
		}

		Node newNode = new Node(node.val);
		nodeToCopy.put(node, newNode);

		for (Node nei : node.neighbors) {
			newNode.neighbors.add(dfs(nei));
		}

		return newNode;
	}
}

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        node_to_copy = {}

        def dfs(node):
            if not node:
                return None

            if node in node_to_copy:
                return node_to_copy[node]

            new_node = Node(node.val, None)
            node_to_copy[node] = new_node

            for nei in node.neighbors:
                new_node.neighbors.append(dfs(nei))

            return new_node

        return dfs(node)

261. Graph Valid Tree

An undirected graph is a tree exactly when it has n - 1 edges and all n nodes are connected. Reject the graph immediately when the edge count differs, build an adjacency list, then run DFS from node 0. Visiting all nodes proves connectivity and, together with the edge count, guarantees there is no cycle.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
	public boolean validTree(int n, int[][] edges) {
		// A valid undirected tree must have exactly n - 1 edges
		// and all n nodes must be connected
		if (edges.length != n - 1) {
			return false;
		}

		List<List<Integer>> adjList = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			adjList.add(new ArrayList<>());
		}

		for (int[] edge : edges) {
			int u = edge[0];
			int v = edge[1];
			adjList.get(u).add(v);
			adjList.get(v).add(u);
		}

		Set<Integer> seen = new HashSet<>();
		dfs(0, adjList, seen);
		return seen.size() == n;
	}

	private void dfs(int node, List<List<Integer>> adjList, Set<Integer> seen) {
		if (seen.contains(node)) {
			return;
		}

		seen.add(node);
		for (int nei : adjList.get(node)) {
			dfs(nei, adjList, seen);
		}
	}
}

from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # A valid undirected tree must have:
        # exactly n-1 edges and all n nodes are connected
        if len(edges) != n-1:
            return False

        adj_list = [[] for _ in range(n)]
        for u, v in edges:
            adj_list[u].append(v)
            adj_list[v].append(u)

        seen = set()

        def dfs(node):
            if node in seen:
                return

            seen.add(node)
            for nei in adj_list[node]:
                dfs(nei)

        dfs(0)
        return len(seen) == n

200. Number of Islands

Every unvisited land cell begins a new connected component. Count it, then DFS through all four-directionally connected land while changing visited cells to water.

class Solution {
	private int R;
	private int C;

	public int numIslands(char[][] grid) {
		R = grid.length;
		C = grid[0].length;
		int count = 0;

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (grid[r][c] == '1') {
					dfs(grid, r, c);
					count++;
				}
			}
		}

		return count;
	}

	private void dfs(char[][] grid, int row, int col) {
		if (row < 0 || row >= R ||
			col < 0 || col >= C ||
			grid[row][col] != '1') {
			return;
		}

		grid[row][col] = '0';
		dfs(grid, row + 1, col);
		dfs(grid, row - 1, col);
		dfs(grid, row, col + 1);
		dfs(grid, row, col - 1);
		// no need to reset grid[row][col] to '1'
	}
}

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        R, C = len(grid), len(grid[0])

        def dfs(row, col):
            if row < 0 or row >= R or col < 0 or col >= C or grid[row][col] != '1':
                return

            grid[row][col] = '0'
            dfs(row+1, col)
            dfs(row-1, col)
            dfs(row, col+1)
            dfs(row, col-1)
            # no need to reset grid[row][col] to 1

        count = 0

        for r in range(R):
            for c in range(C):
                if grid[r][c] == '1':
                    dfs(r, c)
                    count += 1

        return count

733. Flood Fill

Starting from (sr, sc), replace every four-directionally connected cell having the original color. Return immediately when the old and new colors match; otherwise recoloring a cell marks it visited before DFS continues to its neighbors.

class Solution {
	private int R;
	private int C;
	private int oldColor;
	private int color;

	public int[][] floodFill(int[][] image, int sr, int sc, int color) {
		R = image.length;
		C = image[0].length;
		oldColor = image[sr][sc];
		this.color = color;

		if (oldColor == color) {
			return image;
		}

		dfs(image, sr, sc);
		return image;
	}

	private void dfs(int[][] image, int row, int col) {
		if (row < 0 || row >= R ||
			col < 0 || col >= C ||
			image[row][col] != oldColor) {
			return;
		}

		image[row][col] = color;
		dfs(image, row + 1, col);
		dfs(image, row - 1, col);
		dfs(image, row, col + 1);
		dfs(image, row, col - 1);
	}
}

from typing import List

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        R, C = len(image), len(image[0])
        old_color = image[sr][sc]

        if old_color == color:
            return image

        def dfs(row, col):
            if row < 0 or row >= R or col < 0 or col >= C or image[row][col] != old_color:
                return

            image[row][col] = color
            dfs(row+1, col)
            dfs(row-1, col)
            dfs(row, col+1)
            dfs(row, col-1)

        dfs(sr, sc)

        return image

130. Surrounded Regions

An O connected to the board’s edge cannot be captured. Run DFS from every border cell and temporarily mark each reachable O as B. Afterward, change every protected B back to O and every other cell to X.

class Solution {
	private int R;
	private int C;

	public void solve(char[][] board) {
		R = board.length;
		C = board[0].length;

		for (int row = 0; row < R; row++) {
			dfsBoarder(board, row, 0);
			dfsBoarder(board, row, C - 1);
		}

		for (int col = 0; col < C; col++) {
			dfsBoarder(board, 0, col);
			dfsBoarder(board, R - 1, col);
		}

		for (int row = 0; row < R; row++) {
			for (int col = 0; col < C; col++) {
				board[row][col] = board[row][col] != 'B' ? 'X' : 'O';
			}
		}
	}

	private void dfsBoarder(char[][] board, int r, int c) {
		// run dfs from boarder
		if (r < 0 || r > R - 1 ||
			c < 0 || c > C - 1 ||
			board[r][c] != 'O') {
			return;
		}

		board[r][c] = 'B';
		dfsBoarder(board, r + 1, c);
		dfsBoarder(board, r - 1, c);
		dfsBoarder(board, r, c + 1);
		dfsBoarder(board, r, c - 1);
	}
}

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        R, C = len(board), len(board[0])

        def dfsBoarder(r, c):
            # run dfs from boarder
            if r<0 or r>R-1 or c<0 or c>C-1 or board[r][c] != 'O':
                return

            board[r][c] = 'B'
            dfsBoarder(r+1, c)
            dfsBoarder(r-1, c)
            dfsBoarder(r, c+1)
            dfsBoarder(r, c-1)

        for row in range(R):
            dfsBoarder(row, 0)
            dfsBoarder(row, C-1)

        for col in range(C):
            dfsBoarder(0, col)
            dfsBoarder(R-1, col)

        for row in range(R):
            for col in range(C):
                board[row][col] = 'X' if board[row][col] != 'B' else 'O'

417. Pacific Atlantic Water Flow

Reverse the direction of the problem: start DFS from each ocean and move to neighboring cells of equal or greater height. Record cells reachable from the Pacific and Atlantic separately, then return their intersection. Each cell is visited at most once per ocean, giving O(RC) time and O(RC) space.

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int R;
    private int C;
    private int[][] heights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.R = heights.length;
        this.C = heights[0].length;
        this.heights = heights;

        boolean[][] pacific = new boolean[R][C];
        boolean[][] atlantic = new boolean[R][C];

        for (int r = 0; r < R; r++){
            dfs(r, 0, 0, pacific);
            dfs(r, C-1, 0, atlantic);
        }

        for (int c = 0; c < C; c++){
            dfs(0, c, 0, pacific);
            dfs(R-1, c, 0, atlantic);
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int r = 0; r < R; r++){
            for (int c = 0; c < C; c++){
                if(pacific[r][c] && atlantic[r][c]){
                    res.add(List.of(r, c));
                }
            }
        }
        return res;
    }

    private void dfs(int r, int c, int prev, boolean[][] reacheable){
        if (r < 0 || r >= R || c < 0 || c >= C || heights[r][c] < prev || reacheable[r][c] == true){
            return;
        }
        reacheable[r][c] = true;
        dfs(r+1, c, heights[r][c], reacheable);
        dfs(r-1, c, heights[r][c], reacheable);
        dfs(r, c+1, heights[r][c], reacheable);
        dfs(r, c-1, heights[r][c], reacheable);
    }
}

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        R, C = len(heights), len(heights[0])
        pacific = [[False] * C for _ in range(R)]
        atlantic = [[False] * C for _ in range(R)]

        def dfs(r, c, prev, reacheable):
            if r < 0 or r >= R or c < 0 or c >= C or heights[r][c] < prev or reacheable[r][c] == True:
                return

            reacheable[r][c] = True
            dfs(r+1, c, heights[r][c], reacheable)
            dfs(r-1, c, heights[r][c], reacheable)
            dfs(r, c+1, heights[r][c], reacheable)
            dfs(r, c-1, heights[r][c], reacheable)

        for r in range(R):
            dfs(r, 0, 0, pacific)
            dfs(r, C-1, 0, atlantic)

        for c in range(C):
            dfs(0, c, 0, pacific)
            dfs(R-1, c, 0, atlantic)

        res = []
        for r in range(R):
            for c in range(C):
                if pacific[r][c] and atlantic[r][c]:
                    res.append([r, c])

        return res