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:

**Pre-order**: The root node is visited first, followed by the left sub-nodes, then the right sub-nodes**Post-order**: The left sub-nodes are visted first, followed by the right sub-nodes, then the root node**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:

*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:

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 (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 >>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 >>