58.get-DOM-tree-height.md

58. get DOM tree height

Problem

https://bigfrontend.dev/problem/get-DOM-tree-height

Problem Description

Height of a tree is the maximum depth from root node. Empty root node have a height of 0.

If given DOM tree, can you create a function to get the height of it?

For the DOM tree below, we have a height of 4.

<div>
  <div>
    <p>
      <button>Hello</button>
    </p>
  </div>
  <p>
    <span>World!</span>
  </p>
</div>

Can you solve this both recursively and iteratively?

Recursive Solution with DFS

/**
 * @param {HTMLElement | null} tree
 * @return {number}
 */
function getHeight(tree) {
  if (tree === null) {
    return 0;
  }
  return 1 + Math.max(getTreeHeight(tree.left), getTreeHeight(tree.right));
}

Iterative Solution using Stack

/**
 * @param {HTMLElement | null} tree
 * @return {number}
 */
function getHeight(tree) {
  if (tree === null) {
    return 0;
  }

  let maxHeight = 0;
  const stack = [[tree, 1]];

  while (stack.length > 0) {
    const [el, height] = stack.pop();
    maxHeight = Math.max(height, maxHeight);

    for (const child of el.children) {
      stack.push([child, height + 1]);
    }
  }

  return maxHeight;
}

Iterative Solution with BFS

/**
 * @param {HTMLElement | null} tree
 * @return {number}
 */
function getHeight(tree) {
  if (tree === null) {
    return 0;
  }

  let maxHeight = 0;
  const queue = [[tree, 1]];

  while (queue.length > 0) {
    const [el, height] = queue.shift();
    maxHeight = Math.max(height, maxHeight);

    for (const child of el.children) {
      queue.push([child, height + 1]);
    }
  }

  return maxHeight;
}