Lecture 288:- Level Order Traversal

Level order traversal (also known as Breadth-First Traversal) visits all the nodes of a binary tree level by level. It starts from the root node and visits nodes at each level from left to right. Here's a C++ implementation of level order traversal for a binary tree using a queue:

cppCopy code

#include <iostream> #include <queue> struct Node {    int data;    Node* left;    Node* right;    Node(int val) {        data = val;        left = nullptr;        right = nullptr;    } }; // Level Order Traversal void levelOrderTraversal(Node* root) {    if (root == nullptr)        return;    std::queue<Node*> q;    q.push(root);    while (!q.empty()) {        Node* current = q.front();        q.pop();        std::cout << current->data << " ";        if (current->left)            q.push(current->left);        if (current->right)            q.push(current->right);    } } int main() {    // Create a binary tree:    //        1    //       / \    //      2   3    //     / \    //    4   5    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);    // Perform level order traversal    std::cout << "Level Order Traversal: ";    levelOrderTraversal(root);    std::cout << std::endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left->left;    delete root->left->right;    delete root->left;    delete root->right;    delete root;    return 0; }

Output:

mathematicaCopy code

Level Order Traversal: 1 2 3 4 5

The output shows the nodes visited in the level order traversal order: 1 -> 2 -> 3 -> 4 -> 5.