3/1/20

Bfs

Question i was asked at one of my interviews:
You have a tree structure where each node has one or more leaf nodes (children)
Write a function which will write nodes of each level sorted in alternated order:
For example - given situation like this:

The output should be:
A, C, B, D, E, F, G, H
Note C, B is in reverse order!

My First Try

This question caught me unprepared (as usual).
My first step was to implement a tree structure in javascript (since my language is JS)


const tree = {
  name: 'a',
  children: [
    {
      name: 'b',
      children: [
        {
          name: 'd',
          children: []
        },
        {
          name: 'e',
          children: []
        },
        {
          name: 'f',
          children: []
        }       
      ]
    },
    {
      name: 'c',
      children: [
        {
          name: 'g',
          children: []
        },
        {
          name: 'h',
          children: []
        }        
      ]
    }    
  ]
}


My first idea was to store all the nodes im traversing through at some place outside the function (global variable) And use a recursion to loop through the nodes

const arr = {}
function f(tree, level = 0) {
  arr[level] = [...arr[level] || [], tree.name];
  (level % 2 ? tree.children: tree.children.reverse()).forEach(ch => f(ch, level+1))
}
f(tree)
console.log({arr}) // printing all nodes at the end

More Performant Way

Since i learned (in the hard way) that recursion is less performant than usual loop (and all the things you can do with recursion you can do as well using loop), i came up with following solution:


function f(tree, level = 0) {
   let queue = [], sortOrder = true;
   if (!level) queue.push(tree);
   // traversing through all the nodes of the tree
   while (queue.length) {
     let node = queue[0]; // moving to the next node (which is now the first)
     console.log(node.name); // printing node
     if (node.children.length){
        // populting the queue with current node's children
        queue = [...queue, ...node.children.sort((a,b) => (sortOrder? (a>b?1:-1) :(b>a?1:-1)))];        
     }
     
     sortOrder =! sortOrder;
     queue.shift(); // remove the first node from the queue (BFS, "F" is for first )

   }
   console.log('finished')
}
f(tree)

Note: im using here a "queue" data structure where members is added from one side and coming from other (FIFO)

Getting started with docker

It is very simple to get started usig docker. All you need to do-is download the docker desktop for your system Once you get docker syste...