Высота произвольного дерева

Question

Учитывая произвольное дерево, где каждый узел имеет указатель на своего первого дочернего элемента (node.left) и ближайшего брата (node.right), как найти высоту дерева?

Вот что у меня есть:

function height(tree) {
  let h = 0;
  const queue = [[tree.root, 1]]; // pair (Node, depth)
  let n = 0; // use a pointer rather than shifting the array
  while (n < queue.length) {
    const [node, d] = queue[n];
    if (d > h) h = d; // if the current depth is greater then the max height so far, then update the max height
    // Traverse the siblings
    let r = node.right;
    while (r) {
      queue.push([r, d]); // siblings have the same depth
      r = r.right;
    }
    node.left && queue.push([node.left, d + 1]); // traverse the children
    n++; // go to the next Node
  }
  return h;
}

Это не рекурсивно, потому что дерево может быть очень большим, и я получаю ошибки переполнения. Этот код должен работать, но просто хотел узнать, есть ли другой / лучший способ сделать это.

Answer 1

function height(node){
   if(!node) return 0;
   var leftHeight = height(node.left);
   var rightHeight = height(node.right);

   return Math.max(leftHeight, rightHeight) + 1;
}

Лучший подход - использовать рекурсию. Он чистый и читаемый.