Binary Tree Traversal
Binary tree traversal methods can be broadly categorized into two main categories:
- Depth-First Traversal:
- Depth-first traversal explores as far as possible along each branch before backtracking.
- In binary trees, depth-first traversal methods include in-order, pre-order, and post-order traversals.
- Depth-first traversal is often implemented recursively.
- Breadth-First Traversal:
- Breadth-first traversal explores the tree level by level, visiting all the nodes at a given depth before moving to the next depth.
- Also known as level-order traversal, this method typically uses a queue data structure for traversal.
- Breadth-first traversal is not naturally implemented recursively.
Binary tree traversal involves visiting each node in the tree exactly once in a specific order. There are three common types of binary tree traversals: in-order, pre-order, and post-order traversal.
Here’s a brief explanation of each type:
- In-order Traversal: In in-order traversal, the left subtree is visited first, then the current node, and finally the right subtree. In a binary search tree (BST), this traversal visits the nodes in ascending order.
- Pre-order Traversal: In pre-order traversal, the current node is visited first, then the left subtree, and finally the right subtree.
- Post-order Traversal: In post-order traversal, the left subtree is visited first, then the right subtree, and finally the current node.
Here’s how you can implement each traversal recursively in C:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new binary tree node
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// In-order traversal
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// Pre-order traversal
void preOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// Post-order traversal
void postOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
}
// Main function
int main() {
// Create the root node and some sample nodes
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("In-order traversal: ");
inOrderTraversal(root);
printf("\n");
printf("Pre-order traversal: ");
preOrderTraversal(root);
printf("\n");
printf("Post-order traversal: ");
postOrderTraversal(root);
printf("\n");
// Clean up memory
free(root->left->left);
free(root->left->right);
free(root->left);
free(root->right);
free(root);
return 0;
}
Output:
In-order traversal: 4 2 5 1 3
Pre-order traversal: 1 2 4 5 3
Post-order traversal: 4 5 2 3 1
