Parallel Recursive Tree Traversal using Dynamic Parallelism (CPU Paralleli

Objective: Traverse a binary tree using parallelism.

Approach:

• Used recursive depth-first traversal with OpenMP tasks.
• Each child node is processed in a separate parallel task.
• Critical sections are used to avoid output race conditions.

Code Summary:

• #pragma omp parallel starts a parallel region
• #pragma omp single to initiate the root traversal
• #pragma omp task for each child

Code:

// Compile with: g++ tree_traversal.cpp -fopenmp -o tree_traversal

include <iostream>

include <omp.h>

struct Node { int value; Node left; Node right; Node(int val) : value(val), left(nullptr), right(nullptr) {} };

void parallelDFS(Node* root) { if (!root) return;

pragma omp critical

std::cout << “Visited Node: “ << root->value << std::endl;

pragma omp task shared(root)

parallelDFS(root->left);

pragma omp task shared(root)

parallelDFS(root->right); }

int main() { // Example 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); root->right->left = new Node(6);

pragma omp parallel

{

pragma omp single

parallelDFS(root); }

return 0; }

Output: Visited nodes printed in non-sequential order, confirming parallel traversal.