DFS in Binary tree

To understand the Depth-first search in the Binary tree, we first need to know why it is called the Depth-first search.

A binary tree is a hierarchical representation of nodes carrying data. Each node contains three fields, one for storing value which we would pass eventually, and the other two fields store address of the left and right child nodes.

Just like every hierarchical structure, the tree also has one reference point. We call it root, which is the topmost node of the tree and has no parent node. In Binary tree, the root has at most two child nodes.

If you noticed already, the tree is not a linear data structure, we cannot access nodes by indexing as we do in linear data structures(Array, List, Stack).

Then, how we would ever explore this complex-looking structure?

Here, tree traversal algorithms come to rescue. There are mainly two types of techniques we use to traverse a binary tree.

DEPTH FIRST SEARCH

BREADTH FIRST SEARCH

As the name implies, DFS traverse a tree by going in-depth recursively till it can and then backtracking to previously visited node. While BFS traverse a tree level by level.

Imagine, you are in a maze game, you pick one road, mark that one visited so that you don't visit it twice and, explore till you find the endpoint. Once you reach the endpoint, you go back to the previously visited road and start exploring from that point, repeat the procedure till you find the escape.

Well, DFS works exactly the same way.

There are three types of DFS in Tree

• Preorder
• Inorder
• Postorder

Preorder:- Parent →Left →Right

Inorder:- Left →Parent →Right

Postorder:- Left →Right →Parent

As u noticed above, we have written three methods with a slight difference. In the first case, we checked if the Parent exists, and if it does we print the current node data. Then, we move to the second step which recursively calls the Left child and goes on until there is no Left left. Once we reach that point, we move to the right side of the Parent and follow the same procedure.

In the second case, we explore the left side of the Parent first, once we reached the endpoint, the function print the current node data and move towards the Right child.

Similar happens in Postorder, here we explored Left and Right child nodes first then moved back to the Parent node.

Thank you for reading this article, and I hope you enjoyed it.