Write tree traversals-preorder, in order and post order traversals ?
Tree Traversals in Data Structures
Tree traversal is a process of visiting all the nodes in a tree in a specific order. There are three primary types of depth-first tree traversal methods:
Preorder Traversal
Inorder Traversal
Postorder Traversal
Each of these traversals visits the nodes in a different sequence. Below is the explanation and implementation of each traversal method.
1. Preorder Traversal
Preorder traversal visits the nodes in the following order:
Visit the root node.
Traverse the left subtree.
Traverse the right subtree.
Algorithm for Preorder Traversal:
Visit the current node (root).
Traverse the left subtree recursively.
Traverse the right subtree recursively.
Example of Preorder Traversal:
For the following tree:
markdown
Copy
Edit
1
/ \
2 3
/ \
4 5
The preorder traversal would be: 1, 2, 4, 5, 3.
C Code for Preorder Traversal:
c
Copy
Edit
#include
#include
// Definition of Tree Node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to perform preorder traversal
void preorder(struct Node* root) {
if (root != NULL) {
printf(“%d “, root->data); // Visit the node
preorder(root->left); // Traverse the left subtree
preorder(root->right); // Traverse the right subtree
}
}
// Function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int main() {
// Create the tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// Preorder Traversal
printf(“Preorder Traversal: “);
preorder(root);
return 0;
}
2. Inorder Traversal
Inorder traversal visits the nodes in the following order:
Traverse the left subtree.
Visit the root node.
Traverse the right subtree.
Algorithm for Inorder Traversal:
Traverse the left subtree recursively.
Visit the current node (root).
Traverse the right subtree recursively.
Example of Inorder Traversal:
For the same tree:
markdown
Copy
Edit
1
/ \
2 3
/ \
4 5
The inorder traversal would be: 4, 2, 5, 1, 3.
C Code for Inorder Traversal:
c
Copy
Edit
#include
#include
// Definition of Tree Node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to perform inorder traversal
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left); // Traverse the left subtree
printf(“%d “, root->data); // Visit the node
inorder(root->right); // Traverse the right subtree
}
}
// Function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int main() {
// Create the tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// Inorder Traversal
printf(“Inorder Traversal: “);
inorder(root);
return 0;
}
3. Postorder Traversal
Postorder traversal visits the nodes in the following order:
Traverse the left subtree.
Traverse the right subtree.
Visit the root node.
Algorithm for Postorder Traversal:
Traverse the left subtree recursively.
Traverse the right subtree recursively.
Visit the current node (root).
Example of Postorder Traversal:
For the same tree:
markdown
Copy
Edit
1
/ \
2 3
/ \
4 5
The postorder traversal would be: 4, 5, 2, 3, 1.
C Code for Postorder Traversal:
c
Copy
Edit
#include
#include
// Definition of Tree Node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to perform postorder traversal
void postorder(struct Node* root) {
if (root != NULL) {
postorder(root->left); // Traverse the left subtree
postorder(root->right); // Traverse the right subtree
printf(“%d “, root->data); // Visit the node
}
}
// Function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int main() {
// Create the tree
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// Postorder Traversal
printf(“Postorder Traversal: “);
postorder(root);
return 0;
}
Summary of Tree Traversals:
Preorder Traversal: Root → Left → Right
Inorder Traversal: Left → Root → Right
Postorder Traversal: Left → Right → Root
These tree traversal algorithms are fundamental in tree-based data structures and are widely used in various applications, including parsing expressions, file systems, and database indexing.