The trees are the non-linear data structure in which nodes are linked to each other in a hierarchy. We widely use trees to represent hierarchical data, tabular data, text data, etc. A binary tree is a specific type of tree that has at most two children at each node. We can perform the binary tree traversal in multiple ways. In this article, we will understand the different ways and algorithms for binary tree traversal with the help of code in C++.
Binary Tree and Its Uses
The following diagram shows a non-binary and a binary tree.
You should note that a node can have none, one, or two children in a binary tree while in a non-binary tree there is no constraint on the number of children nodes.
The binary tree forms a basis for many data structures that we widely use in practice. Some of these are heap, binary search tree, self-balancing trees, etc. Apart from these, a non-binary tree data structure that we widely use for text applications is the trie data structure.
Types of Binary Tree Traversals
Unlike linear data structures such as arrays, lists, stacks, etc. that we can traverse only sequentially, we can perform the binary tree traversal in multiple ways. Broadly, we can classify the binary tree traversal into two parts, depth-first traversal, and breadth-first traversal. These two types are further classified as given below.
- Depth-first binary tree traversal
- Preorder traversal
- Inorder traversal
- Postorder traversal
- Breadth-first binary tree traversal (Level order traversal)
Let us understand these binary tree traversals one by one. But before that let us first define a data type that we will use to define a node of the tree.
Data Type to Define Node of a Tree
The following ‘struct’ defines a data type that we will use to define a node of the tree. It contains an integer ‘data’ field to store the data and two pointers, left and right, that we will use to store pointers to the left and right child of our binary tree.
struct Node
{
int data;
Node *left;
Node *right;
};Depth-first binary tree traversal
The depth-first binary tree traversal lets you traverse the binary tree starting from the first node (root node) and going to the deepest node first. After reaching the deepest node that has no children, we backtrack to its parent. We do this recursively until all nodes are traversed.
We can divide the depth-first binary tree traversal into three parts. The tree ways only differ by the order they traverse the root node, left subtree, and right subtree.
The time complexity of all the three methods is O(n) where ‘n’ is the total number of nodes in the binary tree.
Let us understand each of these ways.
Pre-order traversal
In the pre-order traversal, we start traversing the binary tree from the first node. We first process the root node, then we move to the left subtree and recursively traverse it. After we have traversed the left subtree completely, we move to the right subtree and recursively traverse it.
Let us say our function to perform preorder traversal is named preorder(). It accepts a pointer to a node as an argument.
We can write down the algorithm of pre-order binary tree traversal as follows.
- If the root node is null, return from the function. It makes sure that we terminate the algorithm without any error. This case will also handle the possibility of an empty tree.
- Process the root node.
- Recursively traverse the left subtree (by calling preorder(root->left)).
- Recursively traverse the right subtree (by calling preorder(root->right)).
The code given below implements the algorithm of pre-order traversal. In our code, we have built and traversed the binary tree given in Fig 1.
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
Node *getNewNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void preorder(Node *root)
{
if(!root)
return;
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
int main()
{
Node *root = getNewNode(1);
root->left = getNewNode(2);
root->right = getNewNode(3);
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
preorder(root);
return 0;
}In the code, we have used a getNewNode() function.
- It creates a new node and initializes its ‘data’ element with the parameter that we pass to it.
- It initializes the left and right child pointers with ‘NULL’ to represent that the new node does not have any children at the moment.
- In this way, we can reuse the code and reduce redundancy. It is a good practice to write reusable code.
The preorder() function performs the actual preorder traversal. The output of the code is given below.
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ g++ preorder.cc
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ ./a.out
1 2 4 5 3 6We can see that the root node has been traversed first followed by the recursive left subtree traversal, then the right subtree has been traversed recursively.
Inorder traversal
In the inorder traversal, we start traversing the binary tree from the first node but before processing the root node, we traverse the left subtree recursively. After we have traversed the left subtree completely, we process the root node and then we move to the right subtree to traverse it recursively.
Let us name our function as the inorder() that accepts a pointer to a tree node as an argument.
We can write down the inorder binary tree traversal algorithm as follows.
- If the root node is null, return from the function.
- Traverse the left subtree recursively (by calling the inorder(root->left)).
- Process the root node.
- Traverse the right subtree recursively (by calling the inorder(root->right)).
Let us see the code that implements the inorder traversal algorithm.
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
Node *getNewNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void inorder(Node *root)
{
if(!root)
return;
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
int main()
{
Node *root = getNewNode(1);
root->left = getNewNode(2);
root->right = getNewNode(3);
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
inorder(root);
return 0;
}The output of the above code is as given below.
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ g++ preorder.cc
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ ./a.out
4 2 5 1 6 3You should note the difference in the output of preorder traversal and the output of inorder traversal.
Post-order traversal
As you might have already guessed, in post-order traversal we start traversing from the first node, but before processing the root node, we traverse the left as well the right subtree recursively. Finally, after completing the traversal of both subtrees, we process the root node.
Let us name our function as the postorder() that accepts a pointer to a tree node as an argument.
We can write the algorithm of post-order tree traversal as follows.
- If the root node is null, we return from the function.
- Traverse the left subtree (by calling postorder(tree->left)).
- Traverse the right subtree (by calling postorder(tree->right)).
- Process the root node.
The code to implement the post-order traversal is given below.
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
Node *getNewNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void postorder(Node *root)
{
if(!root)
return;
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
int main()
{
Node *root = getNewNode(1);
root->left = getNewNode(2);
root->right = getNewNode(3);
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
postorder(root);
return 0;
}The output of the code is given below.
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ g++ preorder.cc
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ ./a.out
4 5 2 6 3 1Till now we have seen the depth-first binary tree traversal algorithms. We will now see the breadth-first binary tree traversal.
Breadth-first Binary Tree Traversal
In the breadth-first binary tree traversal, we traverse the tree one level at a time. It means before traversing the children nodes we must traverse all the nodes of the current level.
The first node is said to be at zero level. The children of the first node are said to be at the first level and so on. Therefore, all the nodes that are at an equal distance from the first node are said to be on the same level. Due to this reason, the depth-first traversal is also called the level order traversal.
To traverse the tree by levels we use a queue data structure to store the nodes of the tree. You might remember that in a queue, nodes are added to the end and removed from the front. Thus, we will traverse all the nodes of a level before we get a node from the next level.
Let us call our function as level_order(). We can write the algorithm as follows.
- If the root is empty, return from the function.
- Define a queue and add the first node (root) to it.
- Loop till there are nodes in the queue.
- Take out a node from the queue.
- Process the node.
- Check if the node’s left child exists, if yes, add it to the queue.
- Check if the node’s right child exists, if yes, add it to the queue.
The time complexity of the above algorithm is O(n) where ‘n’ is the number of nodes in the binary tree.
Let us see the code that implements level order traversal.
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
};
Node *getNewNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void level_order(Node *root)
{
if(!root)
return;
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node *temp = q.front();
q.pop();
cout<<temp->data<<" ";
if(temp->left!=NULL)
q.push(temp->left);
if(temp->right!=NULL)
q.push(temp->right);
}
}
int main()
{
Node *root = getNewNode(1);
root->left = getNewNode(2);
root->right = getNewNode(3);
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
level_order(root);
return 0;
}The output of the above code is as given below.
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ g++ preorder.cc
mohtashim@mohtashim:~/eclipse-workspace/ArticlesCPP$ ./a.out
1 2 3 4 5 6 You can see that if you traverse the binary tree given in fig 1 by levels, you will get the same output as given by the above program.
Conclusion
The binary tree is a very widely used data structure and finds its application in areas such as databases, sorting algorithms, searching algorithms, compilers, etc. Therefore, you would need an efficient way to traverse them.
You should keep in mind that all depth-first traversal methods given in this article are based on recursion. So be careful to count the memory usage of the recursion stack while using them. The non-recursive implementations of these algorithms make use of stacks and queues, have the same space and complexity, and are much more complex.
On the other hand, level order traversal lets you traverse the tree by levels. It can also be implemented using recursion but that makes it very inefficient in time complexity. On the other hand, the method that we have seen in this article for level order traversal is a very simple and efficient method in terms of time and space.
Hope you have enjoyed learning. Keep coming for more articles.
Donate to Avid Python
Dear reader, If you found this article helpful and informative, I would greatly appreciate your support in keeping this blog running by making a donation. Your contributions help us continue creating valuable content for you and others who come across my blog. No matter how big or small, every donation is a way of saying "thank you" and shows that you value the time and effort we put into writing these articles. If you feel that our article has provided value to you, We would be grateful for any amount you choose to donate. Thank you for your support! Best regards, Aditya Founder
If you want to Pay Using UPI, you can also scan the following QR code.
