Depth First Search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Implement Depth First Search for a given input tree.

Recursive solutions

To return an array, first we need an empty array, where we can push our node values when we are done traversing them completely.

  1. Create a helper function depthFirstSearchHelper that takes in an array(solution array that needs to be returned) and the input tree.
  2. If there is no tree (i.e. we have reached the end of a leaf node - !tree) - return from there.
  3. Push the value in the array - array.push(). This will ensure that the element pushed is a leaf node because we returned right before this traversal.
  4. Traverse the left subtree - depthFirstSearchHelper(tree.left, arr)
  5. Traverse the right subtree - depthFirstSearchHelper(tree.right, arr).

This is a simple solution and is pretty straightforward. (beauty of recursion).

Time Complexity:

  • O(N) Time, because we are going to visit every node atmost once.
Solve Depth First Search on Algochurn

Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn