1. Depth First Search (DFS)

Depth First Search has three variations:

1. In-order
2. Pre-order
3. Post-order

Simple DFS code (If Adjacency List is given):

int main() {
    int V = 5;
    vector<vector<int>> adj(V);

    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0};
    adj[3] = {1};
    adj[4] = {1};

	// Recursive
	vector<bool> visited(V, false);
	dfs(0, adj, visited);
	//
	
	// Iterative
    dfs(0, adj);
	//

    return 0;
}

// Recursive
void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;

    // Process the current node
    cout << node << " ";

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

// Iterative
void dfs(int start, vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false); // Track visited nodes
    stack<int> st; // Stack for DFS traversal

    st.push(start); // Push starting node

    while (!st.empty()) { // Continue until stack is empty
        int node = st.top(); // Get the top node
        st.pop(); // Remove it from the stack

        if (visited[node]) continue; // Skip if already visited

        visited[node] = true; // Mark current node as visited

        for (int neighbor : adj[node]) { // Traverse all neighbors
            if (!visited[neighbor]) {    // If neighbor is unvisited
                st.push(neighbor);       // Push it onto the stack
            }
        }
    }
}

Applications

1. Flattening Trees
2. Building or checking structures
3. Searching for nodes based on custom logic