Graph Traversal & Tree Traversal

 

Graph Traversal
Graph traversal means visiting all the vertices (nodes) of a graph in a specific order, usually to process or search data.
It helps in finding paths, connectivity, and other properties in graphs.

There are two main traversal methods:

1. Depth First Search (DFS)
2. Breadth First Search (BFS)

 

1. Depth First Search (DFS)

DFS explores as far as possible along each branch before backtracking.
It uses a stack (can be implemented using recursion).

 

Algorithm (Using Recursion):

DFS(G, v):

    mark v as visited

    for each neighbor u of v:

        if u is not visited:

            DFS(G, u)

Steps:

1. Start from any vertex.
2. Visit and mark it as visited.
3. Move to an adjacent unvisited vertex.
4. Repeat until no unvisited adjacent vertex remains.
5. Backtrack to the previous vertex and continue.

 

Example: Graph:

A - B - C

|      |

D - E

DFS starting from A → A, B, E, D, C

 

DFS Spanning Tree

    A

     |

    B

   /  \

  C  E

        |

       D

 

2. Breadth First Search (BFS)

BFS visits all vertices of a graph level by level.
It uses a queue for its implementation.

Algorithm:

BFS(G, v):

    create a queue Q

    mark v as visited and enqueue it into Q

    while Q is not empty:

        u = dequeue(Q)

        for each neighbor w of u:

            if w is not visited:

                mark w as visited

                enqueue w

Steps:

1. Start from any vertex.
2. Visit and enqueue it.
3. Visit all its unvisited neighbors.
4. Dequeue and continue for next vertex.

Example:

Graph:

A - B - C

|      |

D - E

BFS starting from A → A, B, D, C, E

 

BFS Spanning Tree

     A

    /  \

   B  D

  /  \

 C  E

 

Comparison Between BFS and DFS

Feature	BFS	DFS
Data Structure	Queue	Stack / Recursion
Approach	Level-order traversal	Depth-first traversal
Memory Usage	More (stores all neighbors)	Less (recursion stack)
Path Finding	Finds shortest path in unweighted graphs	Does not guarantee shortest path
Application	Shortest path, Web crawlers	Topological sorting, Solving mazes

Note: A Web Crawler (also called a Spider or Bot) is an automated program that systematically browses the internet to collect data from web pages.

 

Applications of Graph Traversal

• Finding connected components
• Path finding in networks
• Web crawling
• Detecting cycles
• Topological sorting
• AI search algorithms
• Network broadcasting

 

Tree Traversal

Tree traversal means visiting all the nodes of a tree in a specific order exactly once to process or display data.
Each node of a tree can have a left child, a right child, or both.

 

Types of Tree Traversal

Tree traversals are of two main types:

1.Depth First Traversal (DFT)

Visits nodes as deep as possible before backtracking.
Example Tree

        A

       /  \

     B   C

     /  \

    D  E

 

• Inorder Traversal (Left → Root → Right)

Algorithm:

Inorder(node):

    if node is not null:

        Inorder(node.left)

        print(node.data)

        Inorder(node.right)

InOrder: D → B → E → A → C

 

• Preorder Traversal (Root → Left → Right)

Algorithm:

Preorder(node):

    if node is not null:

        print(node.data)

        Preorder(node.left)

        Preorder(node.right)

PreOrder: A → B → D → E → C

 

• Postorder Traversal (Left → Right → Root)

Algorithm:

Postorder(node):

    if node is not null:

        Postorder(node.left)

        Postorder(node.right)

        print(node.data)

PostOrder: D → E → B → C → A

 

2.Breadth First Traversal (BFT)

Visits nodes level by level, also called Level Order Traversal.

 

·         Level Order Traversal (Breadth First Traversal)

Algorithm (using Queue):

LevelOrder(root):

    create an empty queue

    enqueue root

    while queue not empty:

        node = dequeue()

        print(node.data)

        if node.left:

            enqueue(node.left)

        if node.right:

            enqueue(node.right)

Level Order Traversal: A → B → C → D → E

Comparison Table

Traversal Type	Visiting Order	Application
Inorder	Left → Root → Right	Binary Search Trees (sorted output)
Preorder	Root → Left → Right	Copying a tree, expression prefix form
Postorder	Left → Right → Root	Deleting tree, expression postfix form
Level Order	Level by Level	Shortest path, BFS algorithms