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