Level Order Traversal , Sum at Kth Level In Binary Tree in c++

 

Level Order Traversal, also known as Breadth First Traversal, is a method of traversing a binary tree where the root node is visited first, followed by all its children on the same level, and then moving on to the next level. This is in contrast to Depth First Traversal, where nodes are visited in a depth-first manner (i.e., visiting the children of a node before visiting its siblings).

The process of Level Order Traversal can be implemented using a queue data structure. The root node is first added to the queue, and then its children are added in the order of left child followed by right child. The first node in the queue is then removed and its children are added to the queue in the same order. This process continues until the queue is empty, at which point the traversal is complete.

In C++, the implementation of Level Order Traversal can be done using the STL queue template class. The following is an example of how to implement Level Order Traversal in C++:

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int data;
    Node *left;
    Node *right;
};

void levelOrderTraversal(Node *root) {
    queue<Node*> q;
    q.push(root);
    while(!q.empty()) {
        Node *current = q.front();
        cout << current->data << " ";
        q.pop();
        if(current->left != NULL) {
            q.push(current->left);
        }
        if(current->right != NULL) {
            q.push(current->right);
        }
    }
}

In this example, a struct called Node is defined to represent a node in the binary tree. Each Node struct contains an integer data field, as well as pointers to its left and right children. The levelOrderTraversal function takes a pointer to the root node of the binary tree as its argument.

The function first creates a queue of Node pointers and adds the root node to the queue. A while loop is then used to continue traversing the binary tree until the queue is empty. On each iteration of the loop, the front node in the queue is removed and its data is printed to the console. The left and right children of the current node are then added to the queue, if they are not NULL.

Another useful application of Level Order Traversal is finding the sum at a specific level in a binary tree. For example, if we want to find the sum of all the nodes at level 3 of a binary tree, we can use Level Order Traversal to traverse the tree and keep track of the current level as we go. The following is an example of how to implement this in C++:

int sumAtKthLevel(Node *root, int k) {
 int sum = 0;
 int level = 1;
 queue<Node*> q;
 q.push(root);
 q.push(NULL);
 while(!q.empty()) {
 Node *current = q.front();
 q.pop();
 if(current == NULL) {
 if(!q.empty()) {
 q.push(NULL);
 level++; 
 }
        }
 else {
 if(level == k) { 
 sum += current->data;
 } 
 if(current->left != NULL) {
q.push(current->left);
}
if(current->right != NULL) {
q.push(current->right);
}
}
}
return sum;
}

In this example, the sumAtKthLevel function takes a pointer to the root node of the binary tree and an integer k as its arguments. The function initializes a sum variable to 0 and a level variable to 1. It then creates a queue of Node pointers and adds the root node to the queue, followed by a NULL value.
 A while loop is used to continue traversing the binary tree until the queue is empty. On each iteration of the loop, the front node in the queue is removed. If the current node is NULL, this indicates that we have reached the end of a level. The level variable is incremented and a new NULL value is added to the queue to mark the start of the next level. If the current node is not NULL, we check if the current level is equal to k. If it is, we add the current node's data to the sum variable. Finally, the left and right children of the current node are added to the queue, if they are not NULL.
 

After the while loop has completed, the function returns the sum variable, which contains the sum of all the nodes at level k.
 In conclusion, Level Order Traversal is a useful method for traversing a binary tree in a breadth-first manner. It can be implemented in C++ using the STL queue template class. Additionally, it can also be used to find the sum of all the nodes at a specific level in a binary tree. By combining the power of both techniques, one can easily traverse and analyze a binary tree in a more efficient way.