Tree Traversal – BFS and DFS – Introduction, Explanation and Implementation
Traversing a tree refers to visiting each node once. Interestingly, a tree has multiple ways of traversing the nodes, unlike linked list and array which have just one way of traversal.
A tree traversal is classified as two ways that further has sub classification,
1. Breadth first traversal(BFT)/ Breadth Forst Search(BFS):
Breadth first traversing is based on level wise visiting the nodes. First, all nodes at a certain level are traversed then all the nodes of the next level and so on. We use queue to implement this and keep on iterating the items till we find the element or there are no more elements left in the queue to process.
Traversing the above shown tree in BFT way then, we get 10, 20, 30, 40, 50, 50, 60.
Implementation
Assuming we have pointer based implementation of a binary tree as shown. For breadth first traversing, the approach would be
– All the children of a node are visited
– Once children of a node completed, next move to left most child and then towards right child and so on.
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int key;
struct node *left;
struct node *right;
}Node;
/* create a new node */
Node * newNode(int key){
Node *temp;
temp = (Node *)malloc(sizeof(Node));
temp->key = key;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* print all key at given level */
void printLevelKey(Node *p, int level){
if(!p)
return ;
else if(level == 1){
printf("%d ", p->key);
return ;
}
else{
printLevelKey(p->left, level-1);
printLevelKey(p->right, level-1);
}
}
/* finding max level of a tree */
int getMaxLevel(Node *p){
int l;
int r;
if(!p)
return 0;
l = getMaxLevel(p->left);
r = getMaxLevel(p->right);
return l>r?(l+1):(r+1);
}
/*breadth first traversing*/
void breadthFirstTraversing(Node *p){
int maxLevel = getMaxLevel(p);
int i;
if(!p)
return ;
for (i = 1; i <= maxLevel; i++) {
printLevelKey(p, i);
}
}
int main(void) {
Node *root;
root = newNode(10);
root -> left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->right->left = newNode(60);
printf("Breadth First Traversal: ");
breadthFirstTraversing(root);
return 0;
}
Output:-
Breadth First Traversal: 10 20 30 40 50 60
2. Depth first traversing(DFT)/ Depth First Search(DFS)
This is based on depth wise visiting the nodes. First, all nodes on left are traversed then, move to next path towards right side . We use stack to implement this and keep on iterating the items till we find the element or there are no more elements left in the stack to process.
DFT is further classified into three types:
- Preorder
- Inorder
- Postorder
1. Preorder
In this traversing order of processing is that node is processed first, then its left sub-branch and then its right sub-branch.
Traversing is done as follow
– Given node(root) is visited
– Then, left of node is visited
– and Right of node is visited, where a node could be a subtree also.
2. Inorder
In this traversing order of processing is that left sub-branch of node is processed first, then node and then its right sub-branch.
Traversing is done as follow
– Left of given node(root) is visited
– Then, the node is visited
– and Right of node is visited, where a node could be a subtree also.
3. Postorder
In this traversing order of processing is that left sub-branch of node is processed first, then its right sub-branch and then the node itself.
Traversing is done as follow
– Left of given node(root) is visited
– Then, right of given node is visited
– and finally, the given node is visited, where a node could be a subtree also.
Implementation of Inorder, PreOrder and PostOrder traversal
Using recursive function,the three DFT traversal can be achieved efficiently. This implementation will take O(n) time. Consider the below binary tree,
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int key;
struct node *left;
struct node *right;
}Node;
void printPreorder(Node *); /* print preorder sequenece*/
void printInorder(Node *); /* print inorder sequenece*/
void printPostorder(Node *);/* print postorder sequenece*/
/* create a new node */
Node * newNode(int key){
Node *temp;
temp = (Node *)malloc(sizeof(Node));
temp->key = key;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void printPreorder(Node *p){
if(!p)
return ;
printf("%d ", p->key);
printPreorder(p->left);
printPreorder(p->right);
}
void printInorder(Node *p){
if(!p)
return ;
printInorder(p->left);
printf("%d ", p->key);
printInorder(p->right);
}
void printPostorder(Node *p){
if(!p)
return ;
printPostorder(p->left);
printPostorder(p->right);
printf("%d ", p->key);
}
int main(void){
Node *root;
root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->right->left = newNode(60);
printf("Preorder: ");
printPreorder(root);
printf("\nInorder: ");
printInorder(root);
printf("\nPostorder: ");
printPostorder(root);
return 0;
}
Output:-
Preorder: 10 20 40 50 30 60
Inorder: 40 20 50 10 60 30
Postorder: 40 50 20 60 30 10
Note:-
It should be noted, the above implementation is assuming traversal to a binary tree only.
Applications:
- BFT has huge applications, such as finding shortest path, copying garbage collection, peer to peer network, Bipartiteness Test etc. are many.
- Preorder is used to create a copy of binary tree. Also used to get prefix expression.
- Inorder is mostly used to Binary Search Tree
- Postorder is used to get the postfix expression of tree.
Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂