🌲 DFS Masterclass: The Unified Theory of Traversal

1. The Philosophy of DFS: It's Not Just Visiting 🧠

Many people memorize DFS as "go deep, then backtrack." However, DFS is actually a data flow pipeline that allows you to pass information in two distinct directions during a single traversal.

• Direction 1: Root \(\to\) Leaf (The "Preparation" Step) ⬇️

  • When: Before the recursive call.

  • What: Passing constraints, accumulation, or state down to children.

  • Example: "My current sum from root is X. Child, take X and add your value."

• Direction 2: Leaf \(\to\) Root (The "Merge" Step) ⬆️

  • When: After the recursive call returns.

  • What: Aggregating results from children to solve a problem for the parent.

  • Example: "My left child has 5 nodes, my right has 3. Therefore, I am the root of a subtree of size \(5+3+1 = 9\)."

Code Structure for Data Flow

// General Template for "Data Flow" DFS
void dfs(int u, int p, int data_passed_down) {

    // --- STEP 1: PREPARATION (Root -> Child) ⬇️ ---
    // Use 'data_passed_down' to update current state.
    int current_val = data_passed_down + 1; 

    for (int v : adj[u]) {
        if (v == p) continue; // The "Parent Pointer" Rule imposes direction

        // Pass updated data to child
        dfs(v, u, current_val);

        // --- STEP 2: MERGE (Child -> Root) ⬆️ ---
        // The child has finished its work. Now we use its data.
        // subtree_size[u] += subtree_size[v];
    }
}

---

2. Deep Dive: The Stack, The "Shadow", and Linearization 📚

We distinguish between two ways of using a stack to track traversal state. This is where the physical tree structure casts a "Shadow" onto a linear array.

Scenario A: The "Active Path" Stack (Push & Pop) 🥞

If you push a node when entering and pop it when leaving, the stack always contains the path from the Root to the current node.

• Why is this powerful? ⚡

  It gives you \(O(1)\) access to ancestors. You don't need "Binary Lifting" to find the \(K\)-th parent. You just look back in the array.

// Inside DFS:
path_stack.push_back(u); // Push Logic
// ... process ...
path_stack.pop_back();   // Pop Logic

Scenario B: The "History" Stack (Push Only) — The "Shadow" 🌑

If you push nodes but never pop them, you generate a Preorder Linearization. This "flattens" the tree while preserving structural relationships.

• The Concept: When you visit the Root, then Left, then Right, the sequence groups a node and its entire subtree into a contiguous block in the array.

• Why is this powerful? ⚡

  It converts Subtree problems into Array Range problems (often called Euler Tour).

• Property: The subtree of \(u\) corresponds to the range [entry_time[u], exit_time[u]].

void dfs_flatten(int u, int p) {
    entry_time[u] = timer;
    flat_tree.push_back(u); // The "Shadow" grows
    timer++;
    // ... visit children ...
    exit_time[u] = timer - 1; 
}

---

3. The 0/1 Choice: Recursion on Logic (State Space) 🎲

"Recursion on Logic" shines when there is no physical graph at all. DFS can traverse an invisible State Space, such as generating subsets.

The Logic

At every step, you make a branching logical decision. For subsets of \(\{1, 2, 3\}\):

• Choice 1 (Take): Include the number.

• Choice 0 (Leave): Exclude the number.

This creates an invisible binary tree where left edges represent "Taking" and right edges represent "Leaving."

vector<int> subset;
int n = 3; 

void generateSubsets(int i) {
    // Base Case
    if (i == n) { print(subset); return; }

    // Choice 1: Take
    subset.push_back(i);
    generateSubsets(i + 1);

    // Backtrack: Undo the choice
    subset.pop_back();

    // Choice 0: Leave
    generateSubsets(i + 1);
}

---

4. Advanced Strategies: Lazy Propagation & Invariants 🛡️

Lazy Propagation ("The Leader") 👑

How do I add +10 to an entire subtree without visiting every node right now?

• Logic: Don't touch every member. Mark the Leader (root of the subtree) with val[u] += 10.

• Execution: Wait until all updates are done, then run a single DFS to "push" sums from parents to children.

The Degree Invariant ⚖️

One property that never changes is the Degree Sum Formula. This is a crucial sanity check for constructive graph problems.

\[\sum \text{degrees} = 2 \times |Edges|\]

---

5. "Memory Management" for Problem Solving 🧠

A meta-skill for Competitive Programming is managing your "Mental Stack."

• The Problem: Beginners try to hold the entire code flow in their head ("Line 1 does this, Line 2 does this..."). This leads to Mental Stack Overflow.

• The Solution (Inductive Reasoning):

  • Don't memorize the flow. Memorize the State.

  • Trust the Recursion.

  • Analogy: When writing dfs(child), don't simulate it. Assume "It will return the correct answer" (Mathematical Induction).

---

6. Recommended Practice Tasks 🏋️‍♂️

Concept	Problem	Description
Basic Traversal	LeetCode - Sum of Left Leaves	Simple tree traversal.
Grid Traversal	CSES - Grid Paths	Traversing a logical structure (grid) where path constraints define the "tree".
Implicit DAG	SPOJ - ABCPATH	Longest path in a grid by treating valid moves as a DAG.
State Space	LeetCode - Subsets	Direct application of the 0/1 Choice logic.
Structure & Bridges	CSES - Strongly Connected Edges	Requires finding Bridges (critical edges).
Degree Invariant	CSES - Even Outdegree Edges	Constructive problem relying on $\sum \text{deg} = 2 \times