Perform Level Order Traversal on a Binary Tree in C++

Introduction

Level order traversal is a method of traversing a binary tree where we visit the nodes level by level, from left to right. This is also known as a breadth-first search (BFS) approach for binary trees. To achieve this, we use a queue to explore the nodes level by level.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure to represent nodes in the binary tree.
2. Implement a levelOrderTraversal function that uses a queue to perform level order traversal.
3. Implement the main function to create a sample binary tree and test the level order traversal algorithm.

Code Implementation

// C++ program to perform level order traversal on a binary tree

#include <iostream>
#include <queue>  // For using queue in level order traversal
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function to perform level order traversal of the binary tree
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return;  // If the tree is empty, return

    // Create a queue to hold nodes for level order traversal
    queue<TreeNode*> q;

    // Start with the root node
    q.push(root);

    // Continue traversing until the queue is empty
    while (!q.empty()) {
        // Get the front node from the queue
        TreeNode* current = q.front();
        q.pop();  // Remove the front node from the queue

        // Print the value of the current node
        cout << current->val << " ";

        // Enqueue the left child if it exists
        if (current->left != NULL) {
            q.push(current->left);
        }

        // Enqueue the right child if it exists
        if (current->right != NULL) {
            q.push(current->right);
        }
    }
}

// Helper function to insert a new node into the binary tree (for testing purposes)
TreeNode* insert(TreeNode* node, int val) {
    if (node == NULL) return new TreeNode(val);  // If the tree is empty, create a new node

    // Otherwise, recursively insert the value into the left or right subtree
    if (val < node->val)
        node->left = insert(node->left, val);
    else
        node->right = insert(node->right, val);

    return node;
}

int main() {
    /* Sample Binary Tree:
              10
            /    \
           5      15
          / \    /  \
         3   7  12   20
    */

    // Create an empty binary tree
    TreeNode* root = NULL;

    // Insert nodes into the binary tree
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 12);
    root = insert(root, 20);

    // Perform level order traversal
    cout << "Level Order Traversal of the Binary Tree: ";
    levelOrderTraversal(root);
    cout << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary tree. Each node stores a value val and pointers to its left and right children.
2. levelOrderTraversal function: This function performs the level order traversal using a queue:
   • We start by enqueuing the root node.
   • Then, we continuously dequeue nodes from the front of the queue, print their values, and enqueue their left and right children (if they exist).
   • The process repeats until the queue is empty, ensuring that all nodes are visited level by level.
3. insert function: This helper function is used to insert nodes into the binary tree. It adds new nodes at the correct position based on their values relative to the current node.
4. main function: The main function creates a binary tree, inserts several nodes, and then calls the levelOrderTraversal function to print the nodes level by level.

How the Algorithm Works

The level order traversal algorithm works by using a queue to explore nodes level by level:

• We begin by enqueuing the root node.
• At each step, we dequeue the front node and process it by printing its value.
• If the dequeued node has left or right children, they are enqueued to be processed later.
• This ensures that nodes are processed level by level, starting from the root and moving down to the leaves.

Sample Output

If you run the above program with the provided sample binary tree, the output will be:

Level Order Traversal of the Binary Tree: 10 5 15 3 7 12 20 

The output shows the nodes of the binary tree being printed level by level, starting from the root (10) and proceeding through its children and their respective children.

Conclusion

In this program, we implemented level order traversal for a binary tree using C++. The algorithm uses a queue to process nodes in a breadth-first manner, ensuring that nodes are visited in the correct order, starting from the root and moving level by level. The time complexity of this approach is O(N), where N is the number of nodes in the tree, as each node is visited once. The space complexity is O(N) due to the space required to store nodes in the queue.