Algorithm | Tree에서의 BFS와 DFS

Tree 자료구조에서의 깊이우선탐색^{Breadth-first search, BFS}과 너비우선탐색^{Depth-first search, DFS} 코드를 JavaScript로 정리해봤습니다.

본 글에서 사용할 Tree의 자료구조는 다음과 같습니다.

function TreeNode(val = 0, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

전형적인 binary tree의 노드입니다.

또한 함수 bfs(root) 와 dfs(root)는 root를 root 노드로 삼는 트리에서 순회하는 노드의 val을 순서대로 배열에 담아 반환하는 함수입니다.

target 노드를 찾는 등의 방식으로 사용하는 등 용도에 따라 변형하여 활용할 수 있겠습니다.

참고로 BFS와 DFS 둘 다 O(|V| + |E|)의 시간복잡도를 가집니다._{|V|: number of vertices, |E|: number of edges}

BFS

• Queue를 사용하여 구현
• unweighted graph에선 최단 경로를 찾는 알고리즘¹

function bfs(root) {
  let queue = [root];
  let ret = [];
  while(queue.length) {
    let node = queue.shift();
    ret.push(node.val);
    if(node.left) queue.push(node.left);
    if(node.right) queue.push(node.right);
  }
  return ret;
}

DFS

• Recursion 혹은 Stack을 사용하여 구현
• binary tree의 경우 L, V, R을 방문하는 순서에 따라 pre-order / in-order / post-order traverse가 가능²
• backtracking 기법에서 대표적으로 사용

// with recursion
function dfs(root) {
  if(root === null) return [];
  return [...dfs(root.left), root.val, ...dfs(root.right)];
}

// with stack
function dfs(root) {
  let stack  = [];
  let ret = [];
  let node = root;
  while(node || stack.length) {
    while(node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    ret.push(node.val);
    node = node.right;
  }
  return ret;
}

1. weighted graph의 최단 경로는 Dijkstra’s algorithm으로 구할 수 있습니다. ↩

2. 본 글에서는 L-V-R 순으로 순회하는 in-order traverse로 구현했습니다. ↩

Back to top ↑