1. BFS(Breathd First Search)

이번에는 TREE를 가로지르는 방법에 대해서 설명해보겠다. 기본적으로는 두가지 방법이 있다. 수평으로 가로지르는 방법이랑 수직으로 가로지르는 방법이다. 이번에 배울것은 BFS인데 형제NODE를 먼저 방문하고 나서 그 밑의 자식으로 가는 방법이다. 그럼 로직을 살펴보자.

Breadth First Search

-It is algorithms for treaversing or searching tree or graph data structures. It starts at the tree root and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

-- Pseudocode

• Create a queue (this can be an array) and a variable to store the values of nodes visited.
• Place the root node in the queue.
  -- Loop as long as there is anything in the queue.
• Dequeue a node from the queue and push the value of the node into the variable that stores the nodes.
• If there is a left property on the node dequeued - add it to the queue.
• right? add it to the queue.

-- Return the variable that stores the values.

QUEUE를 사용한다. 형제들을 QUEUE에 저장한다음 앞에서 부터 data에 push해야 BFS가 된다. 글 만으로는 이해하기 힘들다.

일단 코드와 그림을 살펴보자.

BFS(tree) {
  var node = tree;
  var queue = [];
  var data = [];
  queue.push(node);
  // length가 0이면 false가 된다. 따라서 0이 아닌 이상은 while이 계속 돌아간다.
  while (queue.length) {
    node = queue.shift();
    data.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return data;
}

예를 들어 아래와 같은 tree가 있다고 하자. 그럼 while이 looping 할떄마다 queue와 data의 모습은 아래와 같이 바뀐다.

      10
    5    7
  8  9 14 11
----------------- first loop
queue = [node 10]
// shift queue from the beginning and push the node val into data
data = [10]
// push the shifted node's children into queue
queue = [node 5, node 7]

-----------------second loop
queue = [node 5, node 7]
// shift queue from the beginning and push the node val into data
data = [10,5]
// push the shifted node's children into queue
queue = [node 7, node 8, node 9]

-----------------third loop
queue = [node 7, node 8, node 9]
// shift queue from the beginning and push the node val into data
data = [10,5,7]
// push the shifted node's children into queue
queue = [ node 8, node 9, node 14, node 11]

-----------------fourth loop
queue = [ node 8, node 9, node 14, node 11]
// shift queue from the beginning and push the node val into data
data = [10,5,7,8 ]
// push the shifted node's children into queue
queue = [node 9, node 14, node 11]
...
//
returned data = [10, 5, 7, 8, 9, 14, 11]

그리고 queue에 모든 node들이 없어질때까지 loop하다가 queue.length = 0 이 되면 while을 빠져나오고 data를 return한다.
queue를 만들고 앞에서 하나씩 가져와서 가져온 node를 분석하는 방식이다. 그럼 아래로 향하는 DFS를 알아보자!

2. DFS(Depth First Search)

이번엔 DFS에 대해 알아보자. DFS는 BFS와 다르게 방향이 여러가지가 있다.

1. 위에서 아래로 가는 법 (Pre)
2. 아래서 위로 가는 법 (Post)
3. 작은 숫자에서 큰숫자로 순서대로 가는 법 (Inorder)

세가지 모두 코드는 거의 똑같다. 따라서 가장 직관적인 1번만 설명하겠다.

로직은 상당히 간단하다.

재귀함수를 사용할건데, root에서 쭉 내려가다가 왼쪽 노드와 오른쪽 노드를 재귀함수에 pass하면 끝!

dfsPre(tree) {
  var arr = [];
  function traverse(node) {
    // if (node === null) return;
    console.log(node.left, node.right);
    arr.push(node.val);
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
  }
  traverse(tree);

  return arr;
}

왼쪽 가지를 다 traverse하면 오른쪽가지를 traverse한다. 그럼 DFS가 된다. 2,3번을 구현하려면 arr.push() 의 위치만 바꾸어 주면 된다.

3. Usage

그럼 BFS와 DFS는 언제 사용하는 게 좋을까? 영어로 정리한걸 일단 먼저 보자

when to use?

1. In case of dense tree

DFS:when there are so many same level siblings in the node. the more nodes spread all around to visit, the more space used up when you choose BFS. But if you use DFS, all you have to do just find one way until you hit the end without anything to store as you go down.

• In order: Used commonly with BST’s. Notice we get all nodes in the tree in their underlying order.

• Pre-order: Can be used to ‘export’ a tree structure so that it is easily reconstructed or copied. you flatten or freeze it in a file. and you can rehydrate it by going through the file to re-create the tree(just like Max Binary Heap).

2. In case of thin tree

BFS:for BFS, as you go down into the leaf, you have something to store, so if there is less branch to visit, then you wouldn’t take much space to store. But in this case, DFS can call self many times so it would take much time compared to BFS.

다시 말하면, 옆으로 넓으면 DFS를 쓰고 밑으로 많이 뻗어있으면 BFS를 쓰는 게 효율적이라는 말이다.

끝!