트리의 너비(Tree Width)

References

아래 링크의 강의 중 Section 26. Tree Width with Level Width의 내용을 추려 이번 글을 작성하였습니다.
The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Tree Width

function levelWidth(root) {
  const arr = [root, "s"];
  const widths = [0];

  while (arr.length > 1) {
    const node = arr.shift();

    if (node === "s") {
      widths.push(0);
      arr.push("s");
    } else {
      arr.push(...node.children);
      widths[widths.length - 1]++;
    }
  }

  return widths;
}

각 단계에 포함된 값들을 arr에 넣어서 배열 arr의 길이를 width로서 저장하고, 중간에 stopper 역할을 하는 문자 s를 넣어 탐색 작업 중 문자 s와 만나면 다음 단계로 넘어가게끔 한다.