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.

Create a helper function depthFirstSearchHelper that takes in an array(solution array that needs to be returned) and the input tree.
If there is no tree (i.e. we have reached the end of a leaf node - !tree) - return from there.
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.
Traverse the left subtree - depthFirstSearchHelper(tree.left, arr)
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

#tree #Recursion #Tree Traversal #Facebook #Google #Youtube #Amazon

Practice all the solutions below

JavaScript (Node.js 12.14.0)

Algochurn Theme

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

00:00:00

Expand Solution

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.

Example

Input

Binary Tree
                1
              /   \
            2       3
          /   \       \
        4       5       7

Output

Array
DFS:  [ 1, 2, 4, 5, 3, 7 ]

Explanation

Since we are traversing the tree depth wise, the first thing we do is to traverse the tree till the bottom i.e. the from the root node to the extreme left leaf node. Oncce there are no children left, we backtrack and traverse the next set of leaf nodes.

Keep in mind it is not the same as Breadth First Search, where we first traverse the siblings / neighbour nodes before we go to the depth.

Constraints

0 <= N <=1000;
N = Node value in a Binary Tree.

Stuck? Check out hints

Try a recursive approach and see how can you get to the leaf node and push the value in the array.

Try creating a helper method where you are going to pass an array and a tree instance. Where do you define your base case? When should the base case be triggered? How to get to the leaf node?

Uploaded by: Manu Arora

Share this problem on

#tree #Recursion #Tree Traversal #Facebook #Google #Youtube #Amazon

Depth First Search

Recursive solutions

Time Complexity:

Practice all the solutions below

Depth First Search

Example

Input

Output

Explanation

Constraints

Stuck? Check out hints

Pages

Algochurn

Frontend Churn

Friends

Links