Binary Tree Level Order Traversal

This exercise builds on Binary Tree Basics and Binary Tree Traversals (preorder/inorder/postorder) and adds a fourth way to visit every node: level order traversal, also called breadth-first traversal. Unlike the other three -- which go deep before wide (depth-first) -- level order visits the tree one level at a time, left to right.

The idea

Preorder/inorder/postorder are naturally recursive because they're depth-first. Level order is breadth-first, so instead of relying on the call stack, it uses an explicit queue:

1. Add the root to a queue, followed by a null marker -- the marker means "end of the current level."
2. Loop while the queue isn't empty: remove the front item.
   • If it's a real node, print it, then enqueue its left and right children (if they exist).
   • If it's the null marker, a full level has just finished: print a newline. If the queue is now empty, stop -- there's nothing left. Otherwise, enqueue another null to mark the end of the level that's about to start.

public void levelOrder(){
    if(root == null){
        return;
    }

    Queue<Node<T>> queue = new LinkedList<>();
    queue.add(root);
    queue.add(null);

    while(!queue.isEmpty()){
        Node<T> node = queue.remove();

        if(node != null){
            System.out.printf(node.data + " , ");
            if(node.left!= null){
                queue.add(node.left);
            }
            if(node.right!= null){
                queue.add(node.right);
            }
        }
        else{
            // We have reached to a new level
            System.out.println();
            if(queue.isEmpty()){
                break;
            }
            queue.add(null);
        }
    }
}

The sample tree

1
|- left: 2
|    |- left: 4
|    |    `- left: 8
|    `- right: 5
|         `- left: 9
`- right: 3
     |- left: 6
     `- right: 7
          |- left: 10
          `- right: 11
               `- right: 12

See the Solutions tab for the full Java implementation.

This is a foundational exercise -- there are no graded test cases for it, since levelOrder() prints rather than returns a value. The level-by-level output below (verified by hand against the tree above) serves as a worked example instead.