From charlesreid1

Breadth-first traversal using queues

Breadth-first traversal: same idea as breadth-first search BFS, except for traversing the tree. So, instead of searching for something in the tree, you're performing a visit action.

When doing BFT, use a queue. The pseudocode looks like this:

add root to queue
while queue not empty:
    remove next item from queue
    perform visit action on item
    add children queue



Traversals on trees:

Breadth-first search and traversal on trees:

  • BFS - breadth first search
  • BFT - breadth first traversal

Depth-first search and traversal on trees:

  • DFS - depth first search
  • DFT - depth first traversal

OOP design patterns: