[Javascript]BFS & DFS

카테고리 설명




정렬되지 않은 이진 트리 전체를 탐색하는 방법에 관한 고찰

1. BFS(넓이 우선 탐색) & DFS(깊이 우선 탐색)

2.BFS(넓이 우선 탐색)

function BFS(root) {
  let node = root;
  const data = [];
  const queue = [];

  queue.push(node);
  while (queue.length) {
    node = queue.shift();
    data.push(node);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return data;
}

3. DFS(깊이 우선 탐색)

//proOrder

function proOrder(root) {
  const data = [];
  function helper(node) {
    data.push(node);
    if (node.left) helper(node.left);
    if (node.right) helper(node.right);
  }
  helper(root);
  return data;
}

function postOrder(root) {
  const data = [];
  function helper(node) {
    if (node.left) helper(node.left);
    if (node.right) helper(node.right);
    data.push(node);
  }
  helper(root);
  return data;
}

function inOrder(root) {
  const data = [];
  function helper(node) {
    if (node.left) helper(node.left);
    data.push(node);
    if (node.right) helper(node.right);
  }
  helper(root);
  return data;
}

4. 각각 언제 사용하는가?

공간복잡도 기준, bfs는 폭이 좁고 깊은거, dfs는 폭이 넓고 얕은거에 쓰는게 좋다.

넓고 얕은 곳에 bfs를 사용하면 queue에 들어가있는 값이 많아지고 메모리도 더 많이 소모. 너무 깊은 곳에 dfs를 사용하면 재귀함수가 쌓여서 메모리를 더 많이 소모

Reference

모던 자바스크립트 deep dive
MDN Data_structures