Tree / Graph Traversal Technique in DSA

Tree and Graph Traversal — Core of DSA Navigation

• Traversal is the process of visiting nodes in a specific order.
• Used in tree/graph problems for search, validation, and processing.
• Common traversal methods: BFS (Breadth-First Search) and DFS (Depth-First Search).

What is Tree/Graph Traversal?

Traversal means visiting all nodes in a tree or graph structure, usually to perform operations like searching, pathfinding, or calculating values.

Traversal helps explore the structure systematically — whether we go deep (DFS) or wide (BFS) depends on the goal and constraints.

Types of Traversal

• Breadth-First Search (BFS) – Visit all neighbors level by level before going deeper.
• Depth-First Search (DFS) – Go deep into one path before backtracking.
• In trees: additional DFS types like Inorder, Preorder, Postorder.

1. Breadth-First Search (BFS)

What is BFS? Breadth-First Search (BFS) is a method used to traverse or search through a graph or tree. The main idea behind BFS is to start from a given node (often called the source or root) and then explore all its immediate neighbors (nodes directly connected to it). After visiting all neighbors at the current level, it moves to the next level of neighbors — hence the name breadth-first.

Why BFS is Important: BFS is useful when you need to find the shortest path in an unweighted graph, or when you want to visit all nodes level by level, like in a tree. It is also the basis for many real-world applications like GPS navigation systems, friend suggestion features on social media, and even solving puzzles or mazes.

How Does BFS Work?

BFS uses a queue data structure to keep track of the nodes to visit next. A queue follows the First-In-First-Out (FIFO) principle — just like a line at a ticket counter. This ensures that nodes are visited in the correct order: first those closest to the start node, then those further away.

Pseudocode

This pseudocode outlines the basic steps of BFS in a very readable way:

function BFS(graph, start):
    create empty queue              // This queue will keep track of nodes to visit
    mark start as visited           // We remember that we’ve already visited this node
    enqueue start                   // Add the starting node to the queue

    while queue not empty:          // While there are still nodes to process
        node = dequeue              // Remove the front node from the queue
        process(node)               // Do something with this node (like print it)

        for each neighbor of node:  // Check each connected node (neighbor)
            if not visited:         // If we haven’t visited it yet
                mark visited        // Mark it as visited to avoid revisiting
                enqueue neighbor    // Add it to the queue to visit later

Step-by-step Example: Imagine a graph where Node A is connected to B and C, and B is connected to D.

• Start at A → visit A, enqueue B and C
• Visit B → enqueue D
• Visit C → no more new neighbors
• Visit D → end

The order of traversal: A → B → C → D

Example Use Cases:

• Shortest path in unweighted graphs: BFS ensures the shortest number of edges to reach a node.
• Level-order traversal in trees: Visit all nodes level by level (first level, then second, and so on).
• Web crawlers, friend recommendations: BFS helps find nearby pages/friends in a network.

Time and Space Complexity:

• Time Complexity: O(V + E)
  You visit each Vertice (node) and each Edge once. So it's very efficient.
• Space Complexity: O(V)
  You store visited nodes and the queue — both grow with the number of vertices.

• BFS explores a graph/tree in layers (breadth-wise).
• It uses a queue to manage the order of node visits.
• Perfect when you want the shortest path or need to visit nodes level-by-level.
• Easy to implement and very common in real-world applications.

2. Depth-First Search (DFS)

What is DFS?

Depth-First Search (DFS) is a method used to traverse or explore a graph or tree structure. The main idea behind DFS is to go as deep as possible into a branch, visiting nodes, and only when you can’t go any further, you backtrack and explore another path.

How it works:

• You start from a selected node (in graphs) or the root (in trees).
• Visit the node and mark it as visited to avoid visiting it again (especially important in graphs).
• Then, for each unvisited neighbor, repeat the same process.
• This continues until all possible paths from the starting node have been explored.

DFS can be implemented in two main ways:

1. Recursive approach: Using function calls to go deeper (easier and natural for trees).
2. Iterative approach: Using a stack data structure to control the traversal manually.

Pseudocode (Recursive)

function DFS(graph, node, visited):
    if node is not visited:
        mark node as visited
        process(node)
        for neighbor in graph[node]:
            DFS(graph, neighbor, visited)

Explanation:

• graph is represented as an adjacency list (each node points to a list of neighbors).
• visited is a set or array to track visited nodes.
• The function visits the node, marks it as visited, processes it (e.g., prints it), and then recursively visits all its unvisited neighbors.

Pseudocode (Iterative)

function DFS(graph, start):
    create empty stack
    mark start as visited
    push start

    while stack not empty:
        node = pop
        process(node)

        for neighbor in graph[node]:
            if not visited:
                mark visited
                push neighbor

Explanation:

• Instead of recursive function calls, we use a stack to keep track of nodes to visit.
• We start with the initial node and push it to the stack.
• While the stack is not empty, pop a node, process it, and push its unvisited neighbors.

Example Use Cases of DFS in Graphs:

• Cycle detection: Check if a graph has any loops.
• Topological sort: Useful in scheduling tasks with dependencies (only works in Directed Acyclic Graphs).
• Connected components: Find all groups of nodes that are connected to each other.
• Maze solving: Traverse paths in games or puzzles.

Time and Space Complexity:

• Time Complexity: O(V + E), where V = number of vertices and E = number of edges. Each node and edge is visited once.
• Space Complexity: O(V), due to recursion stack or the explicit stack and visited set.

---

3. Tree-Specific DFS Traversals

In trees, DFS is commonly split into 3 types of traversal based on the order in which nodes are visited:

Inorder (Left → Node → Right)

function inorder(node):
    if node is not null:
        inorder(node.left)
        process(node)
        inorder(node.right)

Use: In Binary Search Trees (BST), inorder traversal gives sorted order of elements.

Preorder (Node → Left → Right)

function preorder(node):
    if node is not null:
        process(node)
        preorder(node.left)
        preorder(node.right)

Use: Used for copying or serializing the tree structure.

Postorder (Left → Right → Node)

function postorder(node):
    if node is not null:
        postorder(node.left)
        postorder(node.right)
        process(node)

Use: Often used when deleting or freeing nodes in a tree, or evaluating postfix expressions.

Summary of Use Cases:

• Inorder: Retrieves values from BSTs in sorted order.
• Preorder: Tree construction or exporting structure.
• Postorder: Useful for deleting nodes or evaluating trees.

DFS is a foundational concept in both trees and graphs. Understanding how it works will help you solve a wide range of problems — from searching mazes, building compilers, to designing AI for games.

Try visualizing each traversal on paper or using visualization tools to see how the order changes — it makes understanding the patterns much easier!

When to Use BFS vs DFS

Feature	BFS	DFS
Search Type	Level-wise	Depth-wise
Data Structure	Queue	Stack / Recursion
Shortest Path	Yes (Unweighted Graph)	No
Memory Usage	High (due to queue)	Less (recursive stack)
Backtracking	No	Yes

Applications of Graph/Tree Traversal

• Shortest paths (BFS in unweighted graphs)
• Cycle detection (DFS)
• Topological sorting
• Spanning trees (DFS, BFS for MSTs)
• Network flows and connectivity
• Parsing expressions and evaluating trees

Advantages and Disadvantages

BFS Advantages

• Guaranteed shortest path in unweighted graphs
• Systematic level-by-level traversal

DFS Advantages

• Memory efficient on sparse graphs
• Can be implemented with recursion
• Useful for backtracking problems

Disadvantages

• BFS can consume more memory (queue)
• DFS may get stuck in cycles if not handled
• Traversal order varies — needs careful handling for reproducibility

Conclusion

Tree and graph traversal techniques are fundamental for exploring structures in DSA. Whether you're checking paths, finding components, or evaluating nodes, BFS and DFS provide the foundation.

Choose traversal based on your problem — BFS for shortest paths and levels, DFS for depth exploration and recursive solutions. Mastering these will unlock powerful strategies across a wide range of problems.