Do you know “What Are Tree Traversal Algorithms?”ย Have you ever thought about how to implement Tree Traversal Algorithms? Letโs experience how we can use these Algorithms.
But before we jump-start our programming journey, let us know the basic meaning of the word โTraversalโ.
The dictatorial meaning of โTraversalโ is to explore or to roam around. It generally means to go through to every point of a field to explore new things. Like โTraversing In Forestโ means to explore different points of the Forest.
The same thing goes for the programming field also. It means to go through all the nodes of that tree & perform a certain operation. The main action of this is to visit every node of the tree & execute predefined operations.
if you are just getting started with DBMS, you will definitely find grasping this concept helpful. We understand that DBMS can be a difficult concept as it involves coding. Then you can ask for DBMS help online from CodingZap experts.
Summary Of The Article:
- A tree is a non-linear data structure that is made up of two main elements. These are the nodes and the branches.ย
- The node from where the the tree originates is called the root node.ย
- It then branches out to two subtrees: left subtree and right subtree. Each subtree has its own child nodes.
- Tree traversal is a process of visiting each and every node present in a tree in a particular order.ย ย
What Is Tree Traversal In Data Structures?
A tree or a binary tree is a non-linear data structure that originates from a root node or parent node and then gets divided into two subtrees. These are the left subtree and the right subtree. Both the subtrees have children or child nodes.ย
Tree traversal generally means to traverse or visit each node in the tree. We have different methods to perform this. You must select the method carefully, considering the time complexity and the space complexity.
In the further section, I will tell you about the various types of traversal algorithms that you can perform on your binary tree or binary search tree.ย
But before we explore it, let us get to know why is traversing a tree crucial. Read below to know!
What Is The Importance Of Tree Traversal?
In Linear Data Structure, traversal can be in a linear path. That is why it is quite easy to visit every point or node for that type of Data structure.
But in the case of Non-Linear Data Structures, traversing every node is not quite easy. As it is a hierarchical structure visiting every node canโt be in a linear way. This is important to perform certain operations on Trees.
Like one needs to find out the sum of the values of all nodes. Then they need to do a Tree Traversal to complete the process.
Also, it is important from another aspect. Tree Traversal Preorder can be used to sort the nodes of the Binary Tree in ascending order. Tree Traversal Preorder can apply to the Binary Trees only.
A Binary Tree is a type of Tree where the left node value will always be less than the root value. And the right node value will always be greater than the root value.
Types Of Tree Traversal Algorithm:
There are mainly three types of Tree Traversal Algorithms. Depending upon the situation, programmers use any of them. So, let us get to know what tree traversal techniques. First, we will see the three main techniques of Depth-first traversal. These are:
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
Let us know each of the methods briefly one by one.
Still want to learn more about types of tree traversal, then you can check out our article, weโve written a detailed article on it.
Also, if youโre curious to know about types of constraints in linear programming then you can check out our blog section.
1. Inorder Traversal:
This is one type of Tree Traversal Algorithm. Here, in this case, the nodes of the tree will be visited in a particular manner. The procedure will be different from the other Algorithms.
Suppose, we have a tree where the Root node is โNโ, Left Node is โLโ & Right Node is โRโ. so the Tree Traversal Inorder will visit the Root node in the middle of the two sub-nodes. The term โInorderโ represents that the Root node will be inside of those two sub-nodes.
Then the Inorder Traversal sequence will be:
Visit Left Node (L)
Visit Root Node (N)
Visit Right Node (R)
So, the remembering formula will be L-N-R. Remember this formula. This will help to solve many problems in the future.
Let us have a look at the example tree to understand how inorder traversal works. In the below representation, we have a binary tree where the root node is A and it is then divided into left subtree and right subtree by its children nodes B and C.
Let us perform the inorder traversal here by using the L-N-R rule. So, we will first travel to the left subtree upto the last left leaf node i.e. D and then to its parent node B and finally to the right node E.ย
We have now covered the left subtree, thus, we will visit the root node A.ย
Then we will traverse to the right subtree and move to its left leaf node first, then the parent node and finally the right leaf node,
In this way, we will traverse the whole tree. Now, we will see that the order of traversal comes out to be:ย
D-B-E-A-F-C-G
2. Preorder Traversal:
This is another type of Tree Traversal Algorithm. This kind of algorithm is different from the Inorder traversal Algorithm.
Then Preorder Traversal sequence will be:
Visit Root Node (N)
Visit Left Node (L)
Visit Right Node (R)
So, the remembering formula will be N-L-R. Remember this formula. This will help to solve many problems in the future.
Again, considering the above example binary tree. Here, we need to follow the N-L-R rule. How will we do it? Let me help you understand.
Here, first we will visit the root node i.e. A. Next, we will move to the left subtree. After coming here, we will again visit the root node of the left subtree, this is B. Letโs now move to the next level, and towards the left leaf node, i.e D.
Now, it is time to visit the right leaf node, E. We will now come back upwards and go to the right subtree. Visiting its parent node first, i.e., C then F, and finally G.
Thus, the preorder traversal sequence for the given tree is:
A-B-D-E-C-F-Gย
3. Postorder Traversal:
This is the third kind of Tree Traversing Algorithm. This is different from the previous two algorithms. Letโs take the same example for understanding purposes.
In this case, Postorder Traversal will first visit the Left Sub Node. Then it will directly visit the Right Sub Node. At last, it will visit the Root Node. The term โPostorderโ defines that the Root Node will be visited at the last of the Tree Traversal Algorithm.
Then the sequence will be:
Visit Left Node (L)
Visit Right Node (R)
Visit Root Node (N)
So, the remembering formula will be L-R-N. Remember this formula. This will help to solve many problems in the future.
Now, it is time to see what will be the postorder traversal of our example tree.ย
In this technique, we have to first visit the left leaf node, D. Now moving to right leaf node, i.e E and finally the root node B. Similarly, performing it on the right subtree and finally visiting the root node.
The final order of postorder traversal is-
D-E-B-F-G-C-Aย ย ย
Now, let me tell you how can you implement these techniques. Read further to know what are traversals in code.ย
Implementation Of Tree Traversal Algorithm:
Implementation of the Tree Traversal Algorithm is a multistage process. It will go through different functions. Also, one needs to be very clear in function, structure, and pointer to implement such things. Also, knowing the linked list will be a cherry on the cake.
The below tree structure is going to be implemented using the code. The code will first develop the tree. Then it will do Tree Traversal Operations on it. After that, it will provide the result of Tree Traversal.
The above tree will develop after providing value to it. Then the Tree Traversal Algorithms will act on it.
So, first, let us know the steps to implement such algorithms. Here, we are using the C programming language.
Step-1: Create A Treeย
Here, we will start our code by creating a tree. For this, we will define our structure and add functions to it that will create new nodes and assign values to them. Let us see how to do it.
Creating The Structure Of Node:
As we know, a tree is built with a value & some pointer. Here, we have taken an integer value for the info purpose. Also, we have taken two pointers of the type of the certain structure. In this way, we have created a tree structure for further use.
// Structure For A Node Of Tree
struct node
{
// Elements Of A Node
int data;
struct node* left;
struct node* right;
};
Implementing A Function to Create & Develop New Nodes:
Here, using a dynamic memory allocation process, we will create a new node. The size of the node will be equal to the size of the structure of the node. Then the data that we have collected will be inserted into the nodes. At last, the address of the node will be returned to the called function.
/ Process To Create A New Node
struct node* createNode(int data)
{
// Allocate Memory Equivalent To Node Structure And Hold Address In Node Pointer
struct node* newNode = malloc(sizeof(struct node));
// Assigning Data To Nodes
newNode -> data = data;
newNode -> left = NULL;
newNode -> right = NULL;
// Returning The Pointer Value
return newNode;
}
Linking Left & Right Sub Nodes with Root:
ย Here, we will define two different functions. One will add nodes to the Left side of the Root Node. Another will add nodes to the Right side of the Root Node. After that, those functions will return the address of that node to the called function.
// Insert A New Node To Left Of The Given Node
struct node* insertLeft(struct node* root, int data)
{
root -> left = createNode(data);
return root;
}
// Insert A New Node To Right Of The Given Node
struct node* insertRight(struct node* root, int data)
{
root -> right = createNode(data);
return root;
}
Step-2: Function For Implementation Of Inorder Traversalย
Here, as we previously discussed we will follow the LNR rule there. Here, printing the values of the Root Node will be easy. Using the printf() function, we can print the values. But traversing to the Left & Right sub-nodes will be done using the Recursion calling of the function.
// Process Of Inorder Traversal
void inorder(struct node* root)
{
if (root == NULL)
return;
// Recursive Calling To Follow LNR Rule
inorder(root -> left);
printf("%d ", root -> data);
inorder(root -> right);
}
Step-3: Function For Implementation Of Preorder Traversal
ย Here, as we previously discussed we will follow the NLR rule there. Here, printing the values of Root Node can be done using the printf() function. But traversing to the Left & Right sub-nodes will be done using the Recursion calling of the function.
// Process Of Preorder Traversal
void preorder(struct node* root)
{
if (root == NULL)
return;
// Recursive Calling To Follow NLR Rule
printf("%d ", root -> data);
preorder(root -> left);
preorder(root -> right);
}
Step-4: Function For Implementation Of Postorder Traversal
Here, as we previously discussed we will follow the LRN rule there. Here, printing the values of Root Node can be done using the printf() function. But traversing to the Left & Right sub-nodes will be done using the Recursion calling of the function.
// Process Of Postorder Traversal
void postorder(struct node* root)
{
if (root == NULL)
return;
// Recursive Calling To Follow LRN Rule
postorder(root -> left);
postorder(root -> right);
printf("%d ", root -> data);
}
Step-5: Implement The Main Function
Here, we just need to send the values of the Root Nodes as an argument of the functions. Then we will just print the sequence of the Tree Traversal Algorithms.
int main()
{
// Assigning Root Value
struct node* root = createNode(4);
// Assigning Other Brach Values
insertLeft(root, 21);
insertRight(root, 13);
insertLeft(root -> left, 34);
insertRight(root -> left, 0);
insertLeft(root -> right, 18);
insertRight(root -> right, 19);
// Printing The Sequence
printf("Inorder traversal of the Tree is : ");
inorder(root);
printf("\n");
printf("Preorder traversal of the Tree is : ");
preorder(root);
printf("\n");
printf("Postorder traversal of the Tree is : ");
postorder(root);
return 0;
}
Output:
As you can see, our traversal algorithms have followed the rules we mentioned above. For Inorder traversal, we used the L-N-R rule. Similarly, N-L-R and L-R-N rules were used for preorder traversal and postorder traversal respectively.
I hope the above three techniques are clear to you. These techniques are a part of depth-first traversal, which means we reach the leaf node or the deepest level first for travelling.
As a bonus, let me also tell you about another popular traversal technique. The level order traversal, or breadth-first traversal. Let us see what it is and how it is implemented!
What is Level Order Traversal?
The level order traversal is also known as breath-first traversal or breadth-first search. Here, the nodes on one level are traversed or visited, then we move to the next level or the level below the previous one.ย
Let us understand this with the help of our example binary search tree. First, we will start with the root node and then move downwards step by step or level by level.
Thus, after visiting A, we will visit nodes B and C. Further, moving downwards, we will visit the leaf nodes, that are, D,E,F, and G.ย
Let us now see how to implement it using the C programming language.
Implementation Of Level Order Traversal
Here, again, we will have to create our tree and write the main function. The code given above will work for the same in this case as well.ย
We will only see how to write functions for level order traversal or breadth-first search traversal below. Here, we will use the same tree for implementation that we used in implementing the Depth-first traversal techniques.
ย Have a look at the code given below!
// declaring functions
void CurrentLevel(struct node* root, int level);
int heightOfTree(struct node* node);
struct node* newNode(int data);
// Function to print level order traversal a tree
void LevelOrderTraversal(struct node* root)
{
int h = heightOfTree(root);
int i;
for (i = 1; i <= h; i++)
CurrentLevel(root, i);
}
// Print nodes at a current level
void CurrentLevel(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
printf("%d ", root->data);
else if (level > 1) {
CurrentLevel(root->left, level - 1);
CurrentLevel(root->right, level - 1);
}
}
// finding tree height
int heightOfTree(struct node* node)
{
if (node == NULL)
return 0;
else {
// Compute the height of each subtree
int lheight = heightOfTree(node->left);
int rheight = heightOfTree(node->right);
// Use the larger one
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
So, what is happening here? We are first calculating the height of the tree and using it to find the current level. Finally, we are traversing in the level order. For this, we have declared three important functions:
- CurrentLevel()
- heightOfTree()
- LevelOrderTraversal()
In the main function, we are calling the LevelOrderTraversal() function to print the sequence. This can be shown in the output below.
Output:
Let us know see the time complexity of these techniques. Read below for knowing more.
What Is The Time Complexity Of Tree Traversal?
A binary tree or binary seach tree is also considered as a graph in data structures. The time complexity of a graph is O(n+m) where n is the number of nodes and m is the number of edges.
Same goes for binary search trees or a binary tree. Here, since 2 edges are connected to one node, the total edges become n-1.ย
Thus, O(n+n-1) = O(n) for all cases. Whether it is depth-first search or breadth-first search.
As we progress, why donโt we compare DFS and BFS traversal algorithms? Ready for it? Letโs dive in!
Comparison between Depth-First Traversal and Breadth-Frist Traversal Techniques
Depth-First Traversal | Breadth-First Traversal |
Usually utilize stack data structure for traversal. | Utilizes queue data structure for traversal. |
Node is visited depth-wise and then moved to the same level. | The nodes on the same level are visited and then we move to the next level. |
Backtracking is possible after visiting the deepest node. | Backtracking does not occur here. |
May or may not find the shortest path. | It is used to find the shortest path or distance between nodes. |
Generally, have lower space complexity as compared to BFS traversal | Generally, have more space complexity as compared to DFS traversal. |
Example: Inorder, preorder, postorder traversal | Example: Level-order traversal |
Conclusion:
As we saw Tree Traversal Algorithm is very important. We should clear the basics of structure, recursion & function calling for learning the Tree Traversal Algorithm.
Remember the short formulas of the Tree Traversal Algorithms for further problem-solving.
So, hope you have liked this piece of article. Share your thoughts in the comments section and let us know if we can improve more.
We are here to provide you the free guidance about the topic but if you want any programming assistanceย then you can hire professional developers from CodingZap and excel in your DBMS course.
Takeaways:
- Tree traversal is the technique or the process when we visit each node of a binary tree or a binary search tree.
- Depending on your requirements, you can use different approaches.
- The DFS approach includes techniques like inorder, preorder, and postorder traversals.
- The BFS approach includes the level order traversal technique.
- The time complexity for both algorithms is O(n) while the space complexity may differ.
