BFE.dev challenge #58. get DOM tree height

https://bfe.dev is like a LeetCode for FrontEnd developers. I’m using it to practice my skills.

This article is about the coding problem BFE.dev#58. get DOM tree height

Look at the interface

/**
 * @param { HTMLElement | null } tree
 * @returns { number }
 */
function getHeight(tree) {
  // your code here         
}

Height of a tree is the maximum subtree height + 1, so this could be easily done by recursion.

Start coding(recursion)

function getHeight(tree) {
  if (tree === null) return 0
  return Math.max(
    ...Array.from(tree.children).map(getHeight), 
    0
  ) + 1
}

Notice the null case and usage of Math.max(...[]).

rewrite with iteration

When we meet recursion, we should try to rewrite it in iteration.

As we want to get the height, it means to get count of level, so we could just use a queue to solve this.

Here is the basic code.

function getHeight(tree) {
  if (tree === null) return 0
  const queue = [tree]
  let height = 0
  while (queue.length > 0) {
     // TODO
  }
  return height
}

Notice we use a queue array to hold each level. Initially it is the root node.

In the while loop, we do as follows

1. shift all the elements out
2. increment height
3. push all their direct children in the queue.

This leads us to

function getHeight(tree) {
  if (tree === null) return 0
  const queue = [tree]
  let height = 0
  while (queue.length > 0) {
    let count = queue.length
    height += 1
    while (count > 0) {
      const head = queue.shift()
      queue.push(...head.children)
      count -= 1
    }
  }
  return height
}

Passed!

This is easy one. Maybe you can also have a try at https://bfe.dev

Hope it helps, see you next time.