Intro
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:
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:
- a queue
- 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 = [];
queue.push(rootNode);
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 :)
console.log(currentNode.data);
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) {
queue.push(child);
}
}
}
}
Top comments (0)