Tree traversals are fundamental concepts in computer science, especially when dealing with binary trees. They allow us to visit all the nodes of a tree in a specific order. In this blog, I will walk you through three types of tree traversals: Inorder, Preorder, and Postorder
Inorder Traversal
In an inorder traversal, we visit the nodes in this order:
1)Left subtree
2)Root node
3)Right subtree
This traversal is especially useful for binary search trees (BSTs) because it visits the nodes in sorted (ascending) order.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = right = nullptr;
}
};
void inorder(Node* node) {
if (node == nullptr) return;
inorder(node->left); // Visit left subtree
cout << node->data << " "; // Visit root
inorder(node->right); // Visit right subtree
}
int main() {
// Constructing a simple tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Inorder Traversal: ";
inorder(root);
return 0;
}
2. Preorder Traversal
In preorder traversal, the order is:
1)Root node
2)Left subtree
3)Right subtree
This is used in situations where you need to explore nodes before inspecting their children, like creating a copy of the tree.
void preorder(Node* node) {
if (node == nullptr) return;
cout << node->data << " "; // Visit root
preorder(node->left); // Visit left subtree
preorder(node->right); // Visit right subtree
}
int main() {
// Constructing the same tree as before
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Preorder Traversal: ";
preorder(root);
return 0;
}
3. Postorder Traversal
In postorder traversal, the order is:
1)Left subtree
2)Right subtree
3)Root node
This traversal is often used for tree deletion since it ensures that we visit and delete the children before the parent node.
void postorder(Node* node) {
if (node == nullptr) return;
postorder(node->left); // Visit left subtree
postorder(node->right); // Visit right subtree
cout << node->data << " "; // Visit root
}
int main() {
// Constructing the same tree as before
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Postorder Traversal: ";
postorder(root);
return 0;
}
sooooooooooo
- Inorder: Left -> Root -> Right
- Preorder: Root -> Left -> Right
- Postorder: Left -> Right -> Root
Understanding these traversal techniques is crucial when working with binary trees. Practice them well, and you'll find them immensely useful for various tree-based problems in competitive programming! ciaooooo