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.
Binary Tree
1
/ \
2 3
/ \ \
4 5 7
Array
DFS: [ 1, 2, 4, 5, 3, 7 ]
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.
0 <= N <=1000;
N = Node value in a Binary Tree.
Click to reveal
Try a recursive approach and see how can you get to the leaf node and push the value in the array.
Click to reveal
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?