Breadth first

Breadth-First Tree Traversals

There is another mechanism to traverse a tree, which is breadth-first traversal. This process is not recursive, its iterative since we do not go into depth first here we go one layer at a time. We start at the root and go slowly down one by one to the end of the tree.

In the end to achieve the breadth first traversals we use a queue. A queue is an array that the first thing you into is the first thing you get out of it. It works like a FIFO, first in first out, the opposite would be a stack which is first in last out, FILO.

The process behind this is the following, we add the root node to the queue, next we add the left child to the queue, next the right child to the queue. After that, we’ll just dequeue an item off the queue. This we do until there is no item left in the queue.

-> start function by adding root to the queue, queue = [8]
-> process 8, add to final array array = [8]
-> queue 3 and 10 to queue, queue = [3, 10]
-> dequeue 3, queue = [10]
-> queue 3's children, queue = [10, 1]
-> add 3 to final array, array = [8, 3]
-> dequeue 10, queue = [1]
-> queue 10's children, queue = [1]
-> add 10 to final array, array = [8, 3, 10]
-> dequeue 1, queue = []
-> queue 1's children, nothing

final array is [8, 3, 10, 1]