Tree traversal is the process of visiting each node in a tree exactly once. Unlike linear data structures such as an array or linked list which is canonically traversed in linear order, a tree may be traversed in depth-first (in-order, pre-order, and post-order) or breadth-first (level) order

Level Order Traversal

Level order traversal visits all nodes on the same level before going to another lower level

For the above tree, assuming that the left subtree is chosen before the right subtree, level order traversal orders would be 7-2-9-1-3

Implementation example on a binary tree

We can follow these steps to implement a level order traversal algorithm on a binary tree

  • Create a queue Q to track the traversal path

  • Add the root node into Q

  • Do the following while Q still contains at least one node

    • Initialize a list level to cache all nodes in the same level

    • Loop in range of Q's size

      • Remove a node N from Q

      • Add the node value to level

      • Add the left child of N into Q if it is not null

      • Add the right child of N into Q if it is not null

    • Add level to the final list

import com.hellokoding.datastructure.BSTByLinkedList;  
import java.util.*;

public class TreeBreadthFirstTraversal {  
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrderTraversal(BSTByLinkedList.Node root) {
        if (root == null) return res;

        Deque<BSTByLinkedList.Node> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();

            int size = queue.size();
            for (int i=0; i<size; i++) {
                root = queue.remove(); level.add(root.data);
                if (root.left != null) queue.add(root.left);
                if (root.right != null) queue.add(root.right);
            }

            res.add(level);
        }

        return res;
    }

    public static void main(String[] args) {
        BSTByLinkedList tree = new BSTByLinkedList();
        tree.insert(7);
        tree.insert(2);
        tree.insert(3);
        tree.insert(1);
        tree.insert(9);
        List<List<Integer>> result = new TreeBreadthFirstTraversal().levelOrderTraversal(tree.root);
        System.out.println(Arrays.deepToString(result.toArray()));
    }
}

Output

[[7], [2, 9], [1, 3]]

BSTByLinkedList is defined in Binary Search Tree Data Structure

Algorithm