Tree Traversals in a go!
In our past few articles, we have discussed a lot about the latest technologies but we can't really afford to miss out on Data Structures and Algorithms right? In this article, we will be talking about a very important data structure Tree and different operations performed on it.
Tree traversals can be really confusing and sometimes while we are learning it we are not able to understand where will we actually implement it and sometimes we even leave it completely. So let’s go through some traversal techniques and understand the important questions based on them that might help you in an interview :P
📌 Inorder Traversal
I firmly believe that this is the most important traversal because trust me there are so many questions that you can solve just by remembering few points.
So Inorder is LEFT CURRENT RIGHT
In order to find the inorder traversal of the above tree simply move towards the left first then we observe that there is still a node that is present on left hence we move further left side and reach F so now we will get our first element that is F so now out left is explored and move to root element that is E.
While dealing with Binary Search Trees Inorder Traversals can help you with solving many questions because the inorder traversal of a binary search tree is in ascending order if the nodes are numbered from 1 to N.
📌 Level Order Traversal
The second most important traversal technique is Level Order Traversal. I have marked in the diagram below how we define levels . In a particular level we go in ascending order of levels (left to right) and explore it.
If you are aware of Breadth-First-Search or BFS it is a similar concept to that.
LEVEL BY LEVEL
Level 1 is explored and we get C then level 2 we get O D then level 3 we get E C1 H E1 and then finally level 4 we get F. Remember in each level also we are moving from left to right. We can use and manipulate Level Order Traversal in order to solve many questions and once we know this concept solving questions based on this will be a cakewalk.
We usually do level order traversal with the help of a queue and initially push the root node and then keep pushing the left and right children into the queue until the queue is empty and we can store the result in an array or a vector which will give us level order traversal of that tree.
📌 Post-Order Traversal
In this type of traversal, the root node is visited last, and first, we explore the left subtree then the right subtree then the root of the tree. We start from C and then go to O and take it as a new root and traverse in the same way and once we are done traversing the left tree we go to right node D and explore it in the same way and at last, once we are done exploring right and left subtree we print the root.
There can be many other traversals of a tree that is possible but the above three are the ones I find most helpful and if you want to explore other traversals below are a few of the resources which can be helpful:
