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)