1.4) Pre-Order Traversal of Binary Tree

Pre-Order Traversal:

Pre-Order traversal visits nodes of a Binary Tree in the order: Root-Left-Right.

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

Consider this Binary Tree:

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

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

Pre-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 Pre-Order traversal
void preOrderTraversal(Node* root) {
    if (root != nullptr) {
        // Visit the root node (print its data)
        std::cout << root->data << " ";

        // Traverse the left subtree
        preOrderTraversal(root->left);

        // Traverse the right subtree
        preOrderTraversal(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 Pre-Order traversal
    std::cout << "Pre-Order traversal: ";
    preOrderTraversal(root);

    return 0;
}

In this code:

• We define a Node structure for the Binary Tree, holding data, a left child, and a right child.
• The preOrderTraversal function recursively traverses the Binary Tree in Pre-Order order.
• We start by visiting the root node, then traverse the left subtree, and finally the right subtree.

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

This traversal is useful for copying a Binary Tree, as it creates a duplicate tree in the same order.

Pre-Order traversal helps you visit the root node first, followed by the left and right subtrees. This order has its own set of applications in different programming tasks.

Advantages and Use Cases:

1. Copying the Tree: Pre-Order traversal is often used to create a copy of a Binary Tree. As you traverse in the Root-Left-Right order, you can create new nodes to construct a duplicate tree.
2. Expression Reconstruction: If you represent arithmetic expressions in a Binary Tree, Pre-Order traversal helps you reconstruct the original expression. This order ensures that you encounter operators before their operands.

Example Use case: Creating Prefix Expressions:

Pre-Order traversal can be used to create prefix expressions (also known as Polish notation) from an arithmetic expression represented in a Binary Tree. Prefix notation places operators before their operands. When you perform Pre-Order traversal on a Binary Tree representing an arithmetic expression, you can generate the corresponding prefix expression.

For example, given the Binary Tree representing (3 + 4) * 5:

        *
      /   \
     +     5
    / \
   3   4

The Pre-Order traversal sequence is: * + 3 4 5, which is the prefix expression for (3 + 4) * 5.