🧠 EDUCATIONAL CS #4 - Trees, Graphs, and the Difference That Matters

A tree is just a graph with two extra rules: no cycles, and exactly one path between any two nodes.

Tree:                Graph (with cycle):
    1                    1 --- 2
   / \                   |     |
  2   3                  4 --- 3

Why does this distinction matter in interviews?

🔹 In a tree, you never need to track visited nodes during traversal - since there are no cycles, you literally cannot revisit a node.

🔹 In a graph, you MUST track visited nodes, or you risk infinite loops.

python
# Graph DFS - visited set is NOT optional
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

Forgetting the visited set is one of the most common graph-traversal bugs in interviews - code that works perfectly on the example tree-like input, then infinite-loops the moment the interviewer adds one cycle to the test case (which they often do specifically to check this).

Also worth knowing cold: BFS finds the SHORTEST path in an unweighted graph; DFS does not guarantee that. If a problem says "shortest," that's your signal to reach for BFS.

Quick one: is a linked list technically a tree, a graph, both, or neither? 👇