Level Order Traversal of a Binary Tree

Given a binary tree, the task is to print the Level order Traversal of the given tree.

Level Order Traversal is a breadth-first traversal method where nodes of a binary tree are visited level by level, starting from the root. At each level, the nodes are processed from left to right before moving to the next level. This type of traversal ensures that nodes closer to the root are visited before nodes further down in the tree.

Level Order Traversal is also known as Breadth-First Search (BFS) in the context of trees.

Input-Output Examples

Example 1:

  • Input:
plaintext
        1       
       / \      
      2   3     
     / \    
    4   5
  • Output: 1, 2, 3, 4, 5

Example 2:

  • Input:
plaintext
        10       
       /  \      
      20   30     
     / \    
   40  50
  • Output: 10, 20, 30, 40, 50

How Level Order Traversal Works ?

The algorithm uses a queue to facilitate the traversal. The basic idea is to start with the root node, enqueue it, and then continue processing nodes level by level:

  1. Dequeue the front node from the queue and process it.
  2. Enqueue the left child of the dequeued node (if it exists).
  3. Enqueue the right child of the dequeued node (if it exists).
  4. Repeat the above steps until the queue is empty.

Example of Level Order Traversal

cpp
        1
       / \
      2   3
     / \
    4   5

The level order traversal for this tree is:

  1. Visit the root node 1.
  2. Visit the nodes at the second level: 2 and 3.
  3. Visit the nodes at the third level: 4 and 5.

The level order traversal of this tree is: 1, 2, 3, 4, 5.

Here are the implementations of level order traversal in C++, Java, and Python.

C++ Program to implement the Level Order Traversal

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

// Definition of a tree node
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) {
        data = value;
        left = right = nullptr;
    }
};

// Function for level order traversal
void levelOrderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        // Get the front node of the queue
        Node* current = q.front();
        q.pop();

        // Print the current node's data
        cout << current->data << " ";

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

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

// Main function
int main() {
    // Construct the binary 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);

    // Perform level order traversal
    cout << "Level Order Traversal: ";
    levelOrderTraversal(root);

    return 0;
}

Java Program to implement the Level Order Traversal

java
import java.util.LinkedList;
import java.util.Queue;

// Definition of a tree node
class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

public class Main {
    // Function for level order traversal
    public static void levelOrderTraversal(Node root) {
        if (root == null) {
            return;
        }

        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            // Get the front node of the queue
            Node current = q.poll();

            // Print the current node's data
            System.out.print(current.data + " ");

            // Enqueue the left child
            if (current.left != null) {
                q.add(current.left);
            }

            // Enqueue the right child
            if (current.right != null) {
                q.add(current.right);
            }
        }
    }

    public static void main(String[] args) {
        // Construct the binary 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);

        // Perform level order traversal
        System.out.print("Level Order Traversal: ");
        levelOrderTraversal(root);
    }
}

Python Program to implement the Level Order Traversal

python
from collections import deque

# Definition of a tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function for level order traversal
def level_order_traversal(root):
    if root is None:
        return

    q = deque([root])

    while q:
        # Get the front node of the queue
        current = q.popleft()

        # Print the current node's data
        print(current.data, end=" ")

        # Enqueue the left child
        if current.left:
            q.append(current.left)

        # Enqueue the right child
        if current.right:
            q.append(current.right)

# Main function
if __name__ == "__main__":
    # Construct the binary tree
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    # Perform level order traversal
    print("Level Order Traversal: ", end="")
    level_order_traversal(root)

Properties of Level Order Traversal

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is enqueued and dequeued exactly once.
  • Space Complexity: O(w), where w is the maximum width of the tree. The space complexity depends on the number of nodes at the widest level of the tree, which can vary between O(log n) and O(n).
  • Traversal Order: Nodes are processed level by level, from top to bottom and from left to right.

When to Use Level Order Traversal ?

Level Order Traversal is particularly useful when:

  • You want to visit all nodes on the same level before moving to the next level.
  • You are dealing with hierarchical structures like trees where breadth-first processing is required.
  • It’s important to process nodes closest to the root first (e.g., in algorithms like shortest-path search in graphs or trees).

DSA

3133

279

Related Articles