1.3) In-Order traversal of Binary Tree

In-Order Traversal:

In-Order traversal is a way of visiting all nodes of a Binary Tree following a specific order:

Left-Root-Right.

This means you start from the left child, then visit the root, and finally move to the right child.

Consider this Binary Tree:

        5
      /   \
     3     8
    / \   / \
   2   4 6   10

The In-Order traversal sequence for this tree would be: 2, 3, 4, 5, 6, 8, 10.

In-Order Traversal C++:

#include <iostream>

// Define a node structure for the Binary Tree
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to perform In-Order traversal
void inOrderTraversal(Node* root) {
    if (root != nullptr) {
        // Traverse the left subtree
        inOrderTraversal(root->left);

        // Visit the root node (print its data)
        std::cout << root->data << " ";

        // Traverse the right subtree
        inOrderTraversal(root->right);
    }
}

int main() {
    // Creating the Binary Tree
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(8);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->left = new Node(6);
    root->right->right = new Node(10);

    // Perform In-Order traversal
    std::cout << "In-Order traversal: ";
    inOrderTraversal(root);

    return 0;
}

In this code:

• We define a Node structure for the Binary Tree, which holds data, a left child, and a right child.
• The inOrderTraversal function recursively traverses the Binary Tree in In-Order order.
• At each step, we visit the left subtree, then the root node, and finally the right subtree.

When you run the code, it creates the Binary Tree, performs In-Order traversal, and prints the sequence 2, 3, 4, 5, 6, 8, 10.

This traversal is useful for tasks like sorting elements in a Binary Search Tree. It helps you visit the nodes in ascending order.

Advantages and Use Cases:

• Sorting: In-Order traversal on a Binary Search Tree (BST) gives you a sorted list of elements. This is because, in a BST, smaller values are always on the left, and larger values are on the right.
• Expression Evaluation: If you build a Binary Tree to represent arithmetic expressions, In-Order traversal helps you evaluate the expression correctly. It ensures that operations between operands are performed in the correct order.
• Recovering Original Sequence: In some cases, you can use In-Order traversal to recover the original sequence of elements from a Binary Tree.

Example Use case: Expression Evaluation

Consider this Binary Tree that represents the expression (3 + 4) * 5:

        *
      /   \
     +     5
    / \
   3   4

In-Order traversal gives us the sequence 3 + 4 * 5. This order ensures that multiplication is performed after addition, just as we expect in the original expression.