Depth First Search (DFS)

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Tree/graph traversal

• Process of visiting all nodes
• Depth first search (DFS)
• Breadth first search (BFS)

Depth first search - binary trees

• In-order
• Pre-order
• Post-order

In-order traversal

• Order: Left

In-order traversal

• Order: Left -> Current

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal

• Order: Left -> Current -> Right

In-order traversal - implementation

• Order: Left -> Current -> Right

def in_order(self, current_node):

  if current_node:

    self.in_order(current_node.left_child)

    print(current_node.data)

    self.in_order(current_node.right_child)


my_tree.in_order(my_tree.root)

10
20
22
65
68
70
75

• Complexity: $O(n)$
  • $n$ -> number of nodes

Pre-order traversal

• Order: Current

Pre-order traversal

• Order: Current -> Left

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal

• Order: Current -> Left -> Right

Pre-order traversal - implementation

• Order: Root -> Left -> Right

  def pre_order(self, current_node):
    if current_node:
      print(current_node.data)
      self.pre_order(current_node.left_child)
      self.pre_order(current_node.right_child)

my_tree.pre_order(my_tree.root)

65
20
10
22
70
68
75

• Complexity: $O(n)$
  • $n$ -> number of nodes

Post-order

• Order: Left

Post-order

• Order: Left -> Right

Post-order

• Order: Left -> Right -> Current

• Complexity: $O(n)$

  • $n$ -> number of nodes

When to use in-order, pre-order, and post-order

• in-order

  • used BST to obtain the node's values in ascending order

• pre-order

  • create copies of a tree
  • get prefix expressions

• post-order

  • delete binary trees
  • get postfix expressions

Depth first search - graphs

• Graphs can have cycles
  • need to keep track of visited vertices
• Steps:
  1. Start at any vertex
  2. Tracks current vertex to visited vertices list
  3. For each current node's adjacent vertex
     • If it has been visited -> ignore it
     • If it hasn't been visited -> recursively perform DFS

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - graphs

Depth first search - implementation

def dfs(visited_vertices, graph, current_vertex):
    if current_vertex not in visited_vertices:
        print(current_vertex)
        visited_vertices.add(current_vertex)
        for adjacent_vertex in graph[current_vertex]:
            dfs(visited_vertices, graph, adjacent_vertex)

• Complexity: $O(V+E)$
  • $V$ -> number of vertices
  • $E$ -> number of edges

Let's practice!

Data Structures and Algorithms in Python