Level Order Traversal and When to Use BFS or DFS

You are asked to print a tree one row at a time. The root goes on the first line, its children on the second, their children on the third. The three traversals in the previous lesson cannot do this. All three go deep first, so they reach a grandchild before they have seen every child.

Printing a tree by rows needs a different order, called level order traversal. It visits every node at depth 0, then every node at depth 1, and so on. It is also called breadth first search, or BFS, on a tree.

        1
      /   \
     2     3
    / \     \
   4   5     6