How to Implement Level Order Traversal in a Binary Tree

Introduction

Level Order Traversal involves traversing a binary tree level by level from top to bottom and from left to right within each level. This traversal pattern is often referred to as Breadth-First Search (BFS) when applied to trees.

Instead of diving deep into one branch before moving to the next (as in Depth-First Search), Level Order Traversal explores all the nodes at the present depth level before moving on to the nodes at the next level.

Concept Behind the Approach

To perform Level Order Traversal, a queue is commonly used. This data structure supports the First-In-First-Out (FIFO) principle, which helps maintain the order of traversal.

Here’s the basic process:

1. Start by adding the root node to the queue.
2. While the queue is not empty:
   • Remove the front node from the queue.
   • Process its value.
   • Add its left and right children (if they exist) to the queue.

Java Implementation

Below is a simple and clear Java implementation of the Level Order Traversal algorithm using a Queue.

class BinaryNode {
    int key;
    BinaryNode leftBranch;
    BinaryNode rightBranch;

    BinaryNode(int key) {
        this.key = key;
    }
}

public class LevelOrderTraversal {

    public static void printByLayer(BinaryNode startNode) {
        if (startNode == null) return;

        Queue<BinaryNode> pendingNodes = new LinkedList<>();
        pendingNodes.add(startNode);

        while (!pendingNodes.isEmpty()) {
            BinaryNode active = pendingNodes.poll();
            System.out.print(active.key + " ");

            if (active.leftBranch != null) {
                pendingNodes.add(active.leftBranch);
            }

            if (active.rightBranch != null) {
                pendingNodes.add(active.rightBranch);
            }
        }
    }

    public static void main(String[] args) {
        /*
                8
               / \
              4   12
             / \    \
            2   6    14
        */

        BinaryNode treeRoot = new BinaryNode(8);
        treeRoot.leftBranch = new BinaryNode(4);
        treeRoot.rightBranch = new BinaryNode(12);
        treeRoot.leftBranch.leftBranch = new BinaryNode(2);
        treeRoot.leftBranch.rightBranch = new BinaryNode(6);
        treeRoot.rightBranch.rightBranch = new BinaryNode(14);

        System.out.print("Level Order Output: ");
        printByLayer(treeRoot);
    }
}

Example Output

Given the binary tree in the example, the output of the program will be:

1 2 3 4 5 6

Each node is printed as it is visited in level order.

Conclusion

Level Order Traversal is a fundamental technique that’s useful in many applications, such as printing a tree level by level or finding the shortest path in an unweighted tree. The use of a queue makes the process efficient and intuitive. Practicing this pattern helps in understanding more complex tree algorithms later on.

You can find the example code on Github.