Calculate binary tree diameter in linear time - Javascript

binary-tree-diameter.js

"use strict";


class TreeNode {
  data;
  left;
  right;  
  
  constructor(data) {
    this.data = data;
  }
}

const leftRight = {0: "left", 1: "right"}

// const tree = [
//        [1],
//    [2,      3],
//  [n,  4,   5,   6],
//  [   n,n, 7,8, n,n]
// ]
function makeBinaryTree (structure) {
  let root = new TreeNode(structure.shift()[0]);
  let parents = [root]

  for (const row of structure) {
    parents = row.reduce((arr, v, i) => {
      if (v !== null) {
        const node = new TreeNode(v);
        parents[Math.floor(i / 2)][leftRight[i % 2]] = node;        
        arr.push(node);
      }
      
      return arr;
    }, []) 
  }

  return root;
}

let diameter = 0;
let diameterRoot = null;

function postorder(node) {
  if (node === undefined) {
    return 0;
  }
  
  const leftHeight = postorder(node.left);
  const rightHeight = postorder(node.right);
  
  const thisDiameter = leftHeight + rightHeight + 1;
  if (thisDiameter > diameter) {
    diameterRoot = node;
    diameter = thisDiameter;
  }
  
  return Math.max(leftHeight, rightHeight) + 1;
}

const n = null;
const tree = [
       [1],
   [n,      2],
 [        3,   4],
 [       5,6, n, 7]
]


const bt = makeBinaryTree(tree);
postorder(bt)

console.log(bt);
console.log(diameter);
console.log(diameterRoot);