Introduction

Depth First Search (DFS) is a bold search. We go as deep as we can to look for a value, and when there is nothing new to discover, we retrace our steps to find something new.

By the way, DFS always comes with Backtracing and Divide and Conquer.

  • Backtracing: backtracking is the concept of retracing and DFS is the algorithm that implements it.

  • Divide and Conquer: splitting into subproblems of the same type (search in left and right children) until they are simple enough to be solved directly (null nodes or found target) and combine the results from these subproblems (return non-null node).

DFS in tree

Traversal

Preorder Traversal

Root -> Left -> Right

1
2
3
4
5
6
7
8
9
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)

        return  [root.val] + left +  right

Inorder Traversal

Left -> Root -> Right

1
2
3
4
5
6
7
8
9
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)

        return left + [root.val] + right

Postorder Traversal

Left -> Right -> Root

1
2
3
4
5
6
7
8
9
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)

        return left + right + [root.val]

How to make a tree

Class Template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Node:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

# usually using DFS to structure a tree
def build_tree(nodes):
    val = next(nodes)
    if not val or val == 'x': return
    cur = Node(val)
    cur.left = build_tree(nodes)
    cur.right = build_tree(nodes)
    return cur


# yield makes print_tree() as a generator object which is an iterater
def print_tree(root):
    if not root:
        yield "x"
        return
    yield str(root.val)
    yield from print_tree(root.left)
    yield from print_tree(root.right)

if __name__ == '__main__':
    root = build_tree(iter(input().split()))
    print(' '.join(print_tree(new_root)))

DFS in Graph

Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dfs(myGraph, start):
  visited = set()
  def DFSUtil(start, visited):
    # Mark the current node as visited 
    # and print it
    visited.add(start)
    print(start, end=' ')

    # Recur for all the vertices
    # adjacent to this vertex
    for neighbour in myGraph.graph[start]:
        if neighbour not in visited:
            DFSUtil(neighbour, visited)
  DFSUtil(start, visited)

How to make a Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict
# This class represents a directed graph using
# adjacency list representation
class Graph:
    # Constructor
    def __init__(self):
        # Default dictionary to store graph
        self.graph = defaultdict(list)
 
    # Function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)

if __name__ == "__main__":
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)

Reference