We have covered some basics about the tree in the previous posts-
Now let us try to see, how we can traverse a tree. In order to process trees, we need a mechanism for traversing them and that forms the subject of this post. The process of visiting all nodes of a tree is called tree traversal. Each of the nodes is processed only once but they maybe visited more than once. As we have already seen that in linear data structures (like linked lists, stacks, queues etc..), the elements are visited in sequential order. But, in tree data structures there are many different ways.
Tree traversal is like searching the tree except that in traversal the goal is to move through the tree in some particular order. In addition, all nodes are processed in the traversal but searching stops when the required node is found.
Traversal Possibilities
Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps are: performing an action on the current node (referred to as “visiting” the node and it is denoted with “D”), traversing to the left child (denoted with “L”) and traversing to the right child node (denoted with “R”). This process can be easily described through recursion. Based on the above definition there are 6 possibilities:
- LDR : Process left sub-tree -> Process the current node -> Process right sub-tree
- LRD: Process left sub-tree -> Process right sub-tree -> Process the current node
- DLR: Process the current node -> Process left sub-tree -> Process right sub-tree
- DRL: Process the current node -> Process right sub-tree -> Process left sub-tree
- RDL: Process right sub-tree -> Process the current node -> Process left sub-tree
- RLD: Process right sub-tree -> Process left sub-tree -> Process the current node
Classifying the Traversals
The sequence in which these entities are processed defines a particular traversal method. The classification based on the order in which current node is processed. That means, if we are classifying based on current node (D) and if D comes in the middle then it does not matter whether L is on the right side of D or R is on the right side of D. Due to this, the total 6 possibilities were reduced to 3 and they are:
There is another traversal method which does not depend on above orders and it is: