DEV Community

Cover image for Walking a tree (breadth first search)
Konstantinos Blatsoukas
Konstantinos Blatsoukas

Posted on • Updated on

Walking a tree (breadth first search)


A short blog on how you can traverse a tree layer by layer. Breadth first search is an algorithm that does exactly this (also works for graphs, graph is a generalization of a tree)

breadth first search

First, imagine a tree not as a regular tree, but as an a upside down tree (I was really confused about it, because the root is on the top and not at the bottom).

Let's take for example the following tree:

Alt Text

The idea is to traverse the tree layer by layer, in this case:

  • first we visit the first layer, only one node here ''node 1''
  • then the nodes at the second layer, ''node 2'', ''node 3'' and ''node 4''
  • finally, the third layer ''node 5'', ''node 6'' and ''node 7''

js implementation

What is needed for a breadth first implementation in a tree:

  1. a queue
  2. a tree

the algorithm in plain english:

1. initialize an empty queue
2. take the root from the tree
3. add to queue the root node
4. while there are nodes in the queue do:
5.      take/remove the first element of the queue
6.      process the data of the current node
7.      if current node has any children add them to queue

the algorithm in js:

// a node looks like this
rootNode = {
    id: 1,
    data: 1,
    children: [secondNode, thirdNode, forthNode]

function breadthFirstSearch(rootNode) {
    let queue = [];

    while (queue.length !== 0) {
        // remove the first child in the queue
        currentNode = queue.shift();
        // do something cool with the data
        // printing them is also cool :)

        currentChildren = currentNode.children;
        // id there are any children in the node 
        // add them at the end of the queue 
        if (currentChildren !== null) {
            for (const child of currentChildren) {

Top comments (0)