Binary Tree DFS (Depth-First Search)
Tree Selection
Playback Controls
Tree Selection
Leave empty to see full DFS traversal, or enter a number to search for it
Playback Controls
Algorithm Progress
Algorithm Progress
Reference implementation of DFS (Depth-First Search). Select a language tab to view and copy the code.
#include <stdbool.h>
#define MAX 100
bool visited[MAX];
void dfs(int graph[MAX][MAX], int n, int node) {
visited[node] = true;
// process node
for (int i = 0; i < n; i++) {
if (graph[node][i] && !visited[i])
dfs(graph, n, i);
}
}#include <vector>
void dfs(const std::vector<std::vector<int>>& adj,
std::vector<bool>& visited, int node) {
visited[node] = true;
// process node
for (int neighbor : adj[node]) {
if (!visited[neighbor])
dfs(adj, visited, neighbor);
}
}
/* Iterative version using explicit stack */
void dfsIterative(const std::vector<std::vector<int>>& adj, int start) {
std::vector<bool> visited(adj.size(), false);
std::stack<int> stk;
stk.push(start);
while (!stk.empty()) {
int node = stk.top(); stk.pop();
if (visited[node]) continue;
visited[node] = true;
for (int neighbor : adj[node])
if (!visited[neighbor]) stk.push(neighbor);
}
}import java.util.*;
/* Recursive DFS */
public static void dfs(List<List<Integer>> adj,
boolean[] visited, int node) {
visited[node] = true;
// process node
for (int neighbor : adj.get(node)) {
if (!visited[neighbor])
dfs(adj, visited, neighbor);
}
}
/* Iterative DFS */
public static void dfsIterative(List<List<Integer>> adj, int start) {
boolean[] visited = new boolean[adj.size()];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited[node]) continue;
visited[node] = true;
for (int neighbor : adj.get(node))
if (!visited[neighbor]) stack.push(neighbor);
}
}def dfs(adj: list[list[int]], visited: list[bool], node: int) -> None:
visited[node] = True
# process node
for neighbor in adj[node]:
if not visited[neighbor]:
dfs(adj, visited, neighbor)
def dfs_iterative(adj: list[list[int]], start: int) -> list[int]:
visited = [False] * len(adj)
order, stack = [], [start]
while stack:
node = stack.pop()
if visited[node]:
continue
visited[node] = True
order.append(node)
for neighbor in adj[node]:
if not visited[neighbor]:
stack.append(neighbor)
return order/* Recursive DFS */
function dfs(adj, visited, node) {
visited[node] = true;
// process node
for (const neighbor of adj[node]) {
if (!visited[neighbor]) dfs(adj, visited, neighbor);
}
}
/* Iterative DFS */
function dfsIterative(adj, start) {
const visited = new Array(adj.length).fill(false);
const order = [], stack = [start];
while (stack.length) {
const node = stack.pop();
if (visited[node]) continue;
visited[node] = true;
order.push(node);
for (const neighbor of adj[node])
if (!visited[neighbor]) stack.push(neighbor);
}
return order;
}Python — Code Walkthrough
visited passed in — no global state
def dfs(adj, visited, node)Passing visited explicitly avoids global state, making the function pure and testable. Callers can reuse the same visited array across multiple DFS calls (e.g., for disconnected graphs).
Python recursion limit
dfs(adj, visited, neighbor)Python has a default recursion limit of 1000. For large graphs, use sys.setrecursionlimit() or prefer the iterative version to avoid RecursionError.
stack.pop() for LIFO
node = stack.pop()list.pop() removes from the end (O(1)) — LIFO behavior. This is the key difference from BFS which uses deque.popleft() — FIFO behavior.
Check visited on pop in iterative version
if visited[node]: continueMultiple neighbors can push the same node before it is visited. Skipping on pop handles this correctly without extra bookkeeping at push time.