PREREQUISITE(basic knowledge of binary tree-like: what is binary tree why we use binary tree)
This blog is the next step towards learning about binary tree. In this blog, we will learn how to traverse Binary Tree in Inorder Traversal Technique.
Inorder Traversal first encounter left node then root and then traverse to right node.
( LEFT ROOT RIGHT )
Lets understand this by taking an example :
In this example
we are at node A and according to inorder traversal technique we have to traverse to left most node of the root node, so we will move to the left node of node A,
now we are at node B, which is not the left most node, so we continuously move left until we reached left most node . Path will be " A -> B -> C-> D -> E "
when we are at left most node we will mark it as traversed. then acc. to (left root right), we will go to root node of left most node which is "D" then go to "B" because node "D" have not any right node. after reaching "B" we will go to right to node C because all left nodes have already been traversed. then visit node A.
Now, we will traverse right side of node A. We will go to node E. Here node E has left node so we can't marked it as visited or traversed first we have to to traverse left most node of node E which is "H". As we can see H is the left most node so we can't move left , then we will visit node F and at last we will go to node G.
The pattern which we have followed : "EDBCAHFG"
I hope you've got the concept how to do Inorder Traversal in Binary Tree.
now lets walk through the code implemented in C++.
All the best guys :)