5/7/20

Binary Tree Height Exersise

Recently i was at interview and asked following question:
Lest say, there is a binary tree like this:

Write a function which returns a highest level of the tree (in our exmaple is 3)

Solution

Here is a solution i came up with:
My assumption was that node structure has "name" property with node data and "children" with list of pointers to children nodes:


const tree = {
  name: 'a',
  children: [
    {
      name: 'b',
      children: [
        {
          name: 'd',
          children: []
        },
        {
          name: 'e',
          children: [{
               name: 'g',
               children: []
             },{
               name: 'h',
               children: []
             }        
          }]
        }       
      ]
    },
    {
      name: 'c',
      children: [
        {
          name: 'f',
          children: []
        },
        {
          name: 'g',
          children: []
        }        
      ]
    }    
  ]
}
Here is my solution:
I did it iterative way, because recursion can have space complexity issues

 
 function treeHeight(rootnode) {
    let nodes = [rootnode], maxLevel = 1; 
    nodes[0].level = 1;
    // loop through all the nodes
    while(nodes.length) {
       let node = nodes[0]
      
       if (node.children.length) {
         nodes = nodes.concat(node.children.map(ch => {ch.level = node.level + 1; return ch;})); /* if node has children - push them to the end of queue */
       }
       maxLevel = maxLevel < node.level ? node.level : maxLevel;    /* set maxLevel if some node level is bigger;*/
       nodes.shift(); /* remove the first node at each iteration */
    }
  
  	return maxLevel
}

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...