Depth First Search

What is it?

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

How do you do it?

Three methods of DFS:

• Pre Order
• Post Order
• In Order

General Idea

For all three methods:

• you visit a node
• you explore the entire left side
• you explore the entire right side
• traverse the left
• traverse the right

Pre Order

• Create a variable to store values visited, you can use an array to simulate this, something like Data = [ ]
• Create a variable called Current and assign as the root node
• Create a helper function which accepts a node
• Push the value of the node to Data array
• If node has a left property, then call the helper function with the left property of the node
• If node has a right property, then call the helper function with the right property on the node
• Invoke helper function with Current variable
• Return array of values

Here is what the code looks like:

This is what it looks like

Post Order

• Create a variable to store values visited, you can use an array to simulate this, something like Data = [ ]
• Create a variable called Current and assign as the root node
• Create a helper function which accepts a node
• If the node has a left property, then call the helper function with the left property of the node
• If node has a right property, then call the helper function with the right property on the node
• Push the value of the node to Data
• Invoke helper function with Current variable
• Return array of values

Here is what the code looks like:

Here is what it looks like:

In Order

Traverse left entirely until you reach the end of a branch and then visit that node

Traverse right entirely until you reach the end of a branch and then visit that node

• Create a variable called Current and assign as the root node
• Create a helper function which accepts a node
• Create a helper function which accepts a node
• if node has a left property, then call helper function with the left property of the node
• Push the value of the node to Data
• If node has a right property, then call the helper function with the right property on the node
• Invoke helper function with Current variable
• return array of values

Here is what the code looks like:

Big O Time Complexity

The time complexity is O(n) since in all cases you visit each node once.