# DFS and BFS in Tree vs DFS and BFS in Graph

Many beginners think DFS and BFS are the same for Trees and Graphs. The core idea is similar, but there is one very important difference:

> **Graphs can contain cycles, Trees cannot.**

Because of this, Graph traversals usually require a **visited array/set**, while Tree traversals do not.

---

# 1. DFS in Tree

### Idea

Go as deep as possible before coming back.

### Example Tree

```text
        1
      /   \
     2     3
    / \   / \
   4  5  6  7
```

### DFS Order

```text
1 → 2 → 4 → 5 → 3 → 6 → 7
```

### Recursive Code

```cpp
void dfs(TreeNode* root) {

    if(root == NULL) return;

    cout << root->val << " ";

    dfs(root->left);
    dfs(root->right);
}
```

### Why No Visited Array?

Every node has only one parent.

```text
1
|
2
|
3
```

No cycle exists.

---

# 2. DFS in Graph

### Example Graph

```text
0 ----- 1
|       |
|       |
2 ----- 3
```

Adjacency List:

```cpp
0 -> 1,2
1 -> 0,3
2 -> 0,3
3 -> 1,2
```

### Problem Without Visited

```text
0 → 1 → 0 → 1 → 0 → ...
```

Infinite recursion.

### DFS Code

```cpp
void dfs(int node,
         vector<int> adj[],
         vector<int>& visited) {

    visited[node] = 1;

    cout << node << " ";

    for(int nbr : adj[node]) {

        if(!visited[nbr]) {
            dfs(nbr, adj, visited);
        }
    }
}
```

### DFS Traversal

```text
0 → 1 → 3 → 2
```

---

# Tree DFS vs Graph DFS

| Feature             | Tree DFS       | Graph DFS     |
| ------------------- | -------------- | ------------- |
| Visited Array       | ❌ No           | ✅ Yes         |
| Cycles              | ❌ No           | ✅ Possible    |
| Root Node           | Usually exists | May not exist |
| Connected Structure | Always         | May not be    |
| Infinite Loop Risk  | ❌ No           | ✅ Yes         |

---

# 3. BFS in Tree

### Idea

Visit nodes level by level.

### Example

```text
        1
      /   \
     2     3
    / \   / \
   4  5  6  7
```

### BFS Order

```text
1 → 2 → 3 → 4 → 5 → 6 → 7
```

### Code

```cpp
void bfs(TreeNode* root) {

    queue<TreeNode*> q;

    q.push(root);

    while(!q.empty()) {

        TreeNode* node = q.front();
        q.pop();

        cout << node->val << " ";

        if(node->left)
            q.push(node->left);

        if(node->right)
            q.push(node->right);
    }
}
```

### Queue Visualization

```text
[1]

Pop 1
Push 2,3

[2,3]

Pop 2
Push 4,5

[3,4,5]

Pop 3
Push 6,7
```

---

# 4. BFS in Graph

### Example Graph

```text
0 ----- 1
|       |
|       |
2 ----- 3
```

### BFS Traversal

```text
0 → 1 → 2 → 3
```

### Code

```cpp
void bfs(int start,
         vector<int> adj[],
         vector<int>& visited) {

    queue<int> q;

    visited[start] = 1;
    q.push(start);

    while(!q.empty()) {

        int node = q.front();
        q.pop();

        cout << node << " ";

        for(int nbr : adj[node]) {

            if(!visited[nbr]) {

                visited[nbr] = 1;
                q.push(nbr);
            }
        }
    }
}
```

### Why Visited Needed?

Without it:

```text
0 → 1 → 0 → 1 → 0 ...
```

Nodes keep entering the queue.

---

# Tree BFS vs Graph BFS

| Feature             | Tree BFS | Graph BFS  |
| ------------------- | -------- | ---------- |
| Queue Used          | ✅ Yes    | ✅ Yes      |
| Visited Array       | ❌ No     | ✅ Yes      |
| Cycles              | ❌ No     | ✅ Possible |
| Infinite Loop Risk  | ❌ No     | ✅ Yes      |
| Multiple Components | ❌ No     | ✅ Possible |

---

# Complete Picture

```text
TREE

DFS
1
|
v
2
|
v
4
(backtrack)

BFS
1
↓
2 3
↓
4 5 6 7
```

```text
GRAPH

DFS
0 → 1 → 3 → 2

BFS
0 → 1 → 2 → 3

(Visited Array Required)
```

# Interview Question

### Why is a visited array not required in Trees but required in Graphs?

**Answer:**

A Tree is an acyclic connected structure. Every node is reached through exactly one path from the root, so revisiting a node is impossible.

A Graph may contain cycles and multiple paths to the same node. Without a visited array, DFS/BFS can revisit nodes repeatedly and may enter an infinite loop.

---

# Memory Trick

```text
TREE
  No Cycle
  No Visited Array

GRAPH
  Cycle Possible
  Visited Array Required
```

This single rule explains the biggest difference between DFS/BFS on Trees and DFS/BFS on Graphs.


DFS and BFS in Tree vs DFS and BFS in GraphMany beginners think DFS and BFS are the same for Trees and Graphs. The core idea is similar, but there is one very important difference:
Graphs can contain cycles, Trees cannot.
Because of this, Graph trave

Feature	Tree DFS	Graph DFS
Visited Array	❌ No	✅ Yes
Cycles	❌ No	✅ Possible
Root Node	Usually exists	May not exist
Connected Structure	Always	May not be
Infinite Loop Risk	❌ No	✅ Yes

Feature	Tree BFS	Graph BFS
Queue Used	✅ Yes	✅ Yes
Visited Array	❌ No	✅ Yes
Cycles	❌ No	✅ Possible
Infinite Loop Risk	❌ No	✅ Yes
Multiple Components	❌ No	✅ Possible