> Interview Breeze

Depth First Search

Depth first search (sometimes referred to as DFS) is an algorithm for traversing a graph or tree. We traverse the tree or graph by always completely exploring one path before exploring the next path. There are three ways to traverse as a depth first search:

  1. Pre-order: The root node is visited first, followed by the left sub-nodes, then the right sub-nodes
  2. Post-order: The left sub-nodes are visted first, followed by the right sub-nodes, then the root node
  3. In-order: The left sub-nodes are vosoted first, followed by the root node, then the right sub-nodes

For our example, we will illustrate a pre-order traversal of a binary tree:

example Depth First Search of a binary tree

The output of a pre-order traversal of this tree would be 1,2,4,3,5,6

Depth First search can be implemented both recursively as well as non-recursively. When implementing the non-recursive version, you would manage your own stack, as is illustrated in the example below:

Recursive depth first search

def preorder_dfs_print(node):
    print(node.value)
    if node.left: preorder_dfs_print(node.left)
    if node.right: preorder_dfs_print(node.right)

Non-recursive depth first search

def preorder_dfs_print(node):
    stack = [node]
    while len(stack):
        cur_node = stack.pop()
        print(cur_node.value)
        if cur_node.left: stack.append(cur_node.left)
        if cur_node.right: stack.append(cur_node.right)
    return None

You may also want to read:

Discerning a tree from a graph

Write a function that takes a node and returns True if the node is part of a tree or False if it's part of a graph.

Read More >>
Breadth First Search

Breadth first search (sometimes referred to as BFS) is an algorithm for traversing a graph or tree. We traverse the tree or graph by examining all nodes at a given level, before moving on to the next level of nodes.

Read More >>
How to Implement a Quadtree in Python

A Quadtree is a data structure that allows two dimensional data, such as images or matrices, to be represented and traversed as a tree.

Read More >>