Level Order Traversal of a Binary Tree

Given a binary tree, visit all nodes in level order, starting from the root level.

This can be solved by queueing and dequeueing nodes of the tree in a loop. Each node is enqueued, dequeued, and printed once.

The loop runs once for each node, which makes time complexity O(n) for a tree with n nodes.

Implementation

void levelTraversal(Node root) {
    if (root == null)
        return;

Queue q = new Queue();
    q.enqueue(root);

while (Node n = q.dequeue()) {
        print(n.value);

if (n.left)
            q.enqueue(n.left);

if (n.right)
            q.enqueue(n.right);
    }
}

Explanation

• Base Case: If the root is null, return immediately.
• Queue Initialization: A queue is initialized to keep track of the nodes to be visited.
• Traversal Loop: Dequeue a node, print its value, and enqueue its left and right children if they exist.