Tree traversal refers to the process of visiting each node in a tree data structure exactly once in a systematic way. Traversals are essential for performing operations like searching, updating, and printing node values.
Types of Tree Traversals
There are two primary types of tree traversal methods:
- Depth-First Traversal (DFT):
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Breadth-First Traversal (BFT):
- Level Order Traversal
Depth-First Traversals
1. Inorder Traversal (Left, Root, Right)
- Traverse the left subtree.
- Visit the root node.
- Traverse the right subtree.
- Result: Nodes are visited in ascending order for a Binary Search Tree (BST).
C Code
void inorder(struct Node* root) {
if (root == NULL) {
return;
}
inorder(root->left); // Visit left subtree
printf(“%d “, root->data); // Visit root
inorder(root->right); // Visit right subtree
}
2. Preorder Traversal (Root, Left, Right)
- Visit the root node.
- Traverse the left subtree.
- Traverse the right subtree.
- Result: Useful for creating a copy of the tree or prefix notation of expressions.
C Code
void preorder(struct Node* root) {
if (root == NULL) {
return;
}
printf(“%d “, root->data); // Visit root
preorder(root->left); // Visit left subtree
preorder(root->right); // Visit right subtree
}
3. Postorder Traversal (Left, Right, Root)
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root node.
- Result: Useful for deleting the tree or postfix notation of expressions.
C Code
void postorder(struct Node* root) {
if (root == NULL) {
return;
}
postorder(root->left); // Visit left subtree
postorder(root->right); // Visit right subtree
printf(“%d “, root->data); // Visit root
}
Breadth-First Traversal
Level Order Traversal
- Visit nodes level by level from top to bottom.
- Use a queue to implement this traversal.
C Code
#include <stdio.h>
#include <stdlib.h>
// Queue structure for level order traversal
struct Queue {
struct Node* arr[100];
int front, rear;
};
// Enqueue operation
void enqueue(struct Queue* q, struct Node* node) {
q->arr[q->rear++] = node;
}
// Dequeue operation
struct Node* dequeue(struct Queue* q) {
return q->arr[q->front++];
}
// Level order traversal
void levelOrder(struct Node* root) {
if (root == NULL) return;
struct Queue q = {{NULL}, 0, 0};
enqueue(&q, root);
while (q.front < q.rear) {
struct Node* temp = dequeue(&q);
printf(“%d “, temp->data);
if (temp->left) enqueue(&q, temp->left);
if (temp->right) enqueue(&q, temp->right);
}
printf(“\n”);
}
Example Program: Implementing Tree Traversals
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function prototypes
struct Node* createNode(int value);
void inorder(struct Node* root);
void preorder(struct Node* root);
void postorder(struct Node* root);
void levelOrder(struct Node* root);
// Main function
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf(“Inorder Traversal: “);
inorder(root);
printf(“\n”);
printf(“Preorder Traversal: “);
preorder(root);
printf(“\n”);
printf(“Postorder Traversal: “);
postorder(root);
printf(“\n”);
printf(“Level Order Traversal: “);
levelOrder(root);
printf(“\n”);
return 0;
}
// Create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Inorder Traversal
void inorder(struct Node* root) {
if (root == NULL) return;
inorder(root->left);
printf(“%d “, root->data);
inorder(root->right);
}
// Preorder Traversal
void preorder(struct Node* root) {
if (root == NULL) return;
printf(“%d “, root->data);
preorder(root->left);
preorder(root->right);
}
// Postorder Traversal
void postorder(struct Node* root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf(“%d “, root->data);
}
// Level Order Traversal
void levelOrder(struct Node* root) {
if (root == NULL) return;
struct Queue {
struct Node* arr[100];
int front, rear;
} q = {{NULL}, 0, 0};
enqueue(&q, root);
while (q.front < q.rear) {
struct Node* temp = dequeue(&q);
printf(“%d “, temp->data);
if (temp->left) enqueue(&q, temp->left);
if (temp->right) enqueue(&q, temp->right);
}
}
// Enqueue operation
void enqueue(struct Queue* q, struct Node* node) {
q->arr[q->rear++] = node;
}
// Dequeue operation
struct Node* dequeue(struct Queue* q) {
return q->arr[q->front++];
}
Output
Given the tree:
1
/ \
2 3
/ \
4 5
The output will be:
yaml
Copy code
Inorder Traversal: 4 2 5 1 3
Preorder Traversal: 1 2 4 5 3
Postorder Traversal: 4 5 2 3 1
Level Order Traversal: 1 2 3 4 5
Applications of Tree Traversals
- Inorder Traversal: Sorting nodes of a BST.
- Preorder Traversal: Copying or serializing the tree.
- Postorder Traversal: Deleting or evaluating expressions in an expression tree.
- Level Order Traversal: Breadth-first search applications like shortest path in graphs.