javascript_algorithm / 데이터 구조 / 4.6 Tree Traversal

Jul 21, 2025

4.6Tree Traversal

트리를 순회하는 방식인 너비 우선 탐색과 깊이 우선 탐색

TL;DR

추억의 쪽지 시험

Tree Traversal(트리 순회)

트리의 모든 노드를 순회하는 방법에 대한 장이다. 다양한 방법들이 있으나 모두 재귀적 방법을 사용한다. 트리 순회에는 크게 두 가지 방식이 있다.

Breadth First Search: 너비를 우선한다. 즉, 트리의 깊이를 내려가기 전에 우선 해당 층을 전부 순회한다.
Depth First Search(DFS): 깊이를 우선한다. 즉, 트리의 한 층을 순회하기 전에 가장 깊은 곳에서 시작한다.

Breadth First Search(너비 우선 탐색)

BFS는 큐(Queue, FIFO 구조)를 사용해 트리의 각 층(level)들을 순회한다. 수도 코드를 짠다면 아래와 같다:

큐(FIFO 형태의 데이터 구조)를 만들고, 방문한 노드의 값들을 저장하기 위한 변수를 만든다.
루트 노드를 큐에 저장한다.
큐가 빌 때까지 아래의 루프를 반복한다:
- 큐의 노드를 dequeue하며, 그렇게 빠진 노드의 값을 변수에 저장한다.
- 빠진 노드에 left 속성에 해당하는 데이터가 있다면 그걸 큐에 넣는다.
- 빠진 노드에 right 속성에 해당하는 데이터가 있다면 그걸 큐에 넣는다.
값을 저장한 결과 배열을 반환한다.

BFS의 javascript 구현

편의상 이전 포스팅에서 만든 Binary Search Tree를 활용한다.

javascript
BFS(){
  const data = [];
  const queue = [];
  let node = this.root;
  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;
}

Depth First Search(깊이 우선 탐색)

DFS는 스택(Stack, LIFO 구조의 데이터)을 이용해 트리의 끝까지 내려간 후, 다시 돌아오며 다른 가지들을 탐색하는 것으로 3가지 종류가 있다. 3가지 종류는 서로 다른 순서로 노드를 방문한다. 서로의 순서를 비교하기 위해 아래의 tree를 예로 들어보자.

bash
     10
  6     15
3   8      20

1. PreOrder(전위 순회) 방식

PreOrder는 루트 노드부터 시작해, 왼쪽을 들렀다가 오른쪽으로 찾아가는 방식이다. 수도 코드를 작성하면 아래와 같다:

방문한 노드의 값들을 저장하기 위한 변수를 만든다.
노드를 받아서 처리하는 헬퍼 함수를 만든다:
- 이 함수는 우선 노드의 값을 저장하는 변수에 값을 저장한다.
- 다음으로, left가 있다면 left 노드를 헬퍼 함수로 실행한다.
- right가 있다면 right 노드를 헬퍼 함수로 실행한다.
루트를 헬퍼 함수로 실행한다.

javascript
DFSPreOrder(){
  const data = [];
  function traverse(node){
    data.push(node.value);
    if(node.left) traverse(node.left);
    if(node.right) traverse(node.right);
  }
  traverse(this.root);
  return data;
}

BinarySearchTree.DFSPreOrder(); // [10, 6, 3, 8, 15, 20]

DFSPreOrder를 실행하고 브라우저에서 브레이크포인트를 걸고 콜스택의 스텝을 하나씩 진행해보면, 아래와 같은 순서로 순회가 진행된다:

맨 처음에 우선 루트(10)를 push한다.
이후 루트에는 node.left(6)가 있으므로 이를 루트로 하는 traverse가 실행, 해당 traverse의 루트인 6을 push한다.
- 이후 해당 루트인 6엔 node.left(3)이 있으므로 3을 루트로 하는 traverse가 실행, 해당 traverse의 루트인 3을 push한다.
  - 이후 3이 루트인 traverse는 node.left나 node.right는 없다. 따라서 3을 루트로 하는 traverse는 종료.
- 6이 루트인 traverse는 아직 끝나지 않았다. node.right(8)이 있으므로 8을 루트로 하는 traverse가 실행, 이는 3과 같은 결과다.
- 6이 루트인 traverse 종료.
이후 루트의 node.right(15)로 들어갈 차례다.
...

2. PostOrder 방식(후위 순회)

PostOrder는 루트 노드를 가장 마지막에 방문하는 방식이다. PreOrder와 사실 굉장히 비슷한데, 헬퍼 함수에서 노드의 값을 저장하는 변수에 값을 저장하는 순서만 다르다. 수도 코드를 작성하면 아래와 같다:

방문한 노드의 값들을 저장하기 위한 변수를 만든다.
노드를 받아서 처리하는 헬퍼 함수를 만든다:
- 다음으로, left가 있다면 left 노드를 헬퍼 함수로 실행한다.
- right가 있다면 right 노드를 헬퍼 함수로 실행한다.
- 이 함수는 그리고 마지막으로 노드의 값을 저장하는 변수에 값을 저장한다.
루트를 헬퍼 함수로 실행한다.

javascript
DFSPostOrder(){
  const data = [];
  function traverse(node){
    if(node.left) traverse(node.left);
    if(node.right) traverse(node.right);
    data.push(node.value); // PreOrder와 비교하면 여기만 다르다!
  }
  traverse(this.root);
  return data;
}

BinarySearchTree.DFSPostOrder(); // [3, 8, 6, 20, 15, 10]

DFSPostOrder를 실행하고 브라우저에서 브레이크포인트를 걸고 콜스택의 스텝을 하나씩 진행해보면, 아래와 같은 순서로 순회가 진행된다:

맨 처음에 우선 루트(10)를 traverse한다. 하지만 아직 값을 저장하는 변수에 저장하진 않는다.
이후 루트에는 node.left(6)가 있으므로 이를 루트로 하는 traverse가 실행, 해당 traverse의 루트인 6으로 가지만 이를 저장하진 않는다.
- 이후 해당 루트인 6엔 node.left(3)이 있으므로 3을 루트로 하는 traverse가 실행한다. 물론 이를 아직 저장하지 않는다.
  - 이후 3이 루트인 traverse는 node.left나 node.right는 없다. 따라서 3을 변수에 저장하고, traverse를 마친다.
- 6이 루트인 traverse는 아직 끝나지 않았다. node.right(8)이 있으므로 8을 루트로 하는 traverse가 실행, 이는 3과 같은 결과다. 8을 저장한다.
- 6이 루트인 traverse는 6을 저장하고 종료된다.
이후 루트의 node.right(15)로 들어갈 차례다.
...

3. InOrder(중위 순회) 방식

InOrder는 맨 왼쪽부터 노드들을 순서대로 방문하는 방식이다. 덕분에 Binary Search Tree에선 방문한 노드를 저장하는 변수(반환하는 결과)는 트리의 노드들을 순서대로 정렬한 값을 반환한다. 이 방식 역시 PreOrder, PostOrder와 거의 비슷하다. 수도 코드를 작성하면 아래와 같다:

방문한 노드의 값들을 저장하기 위한 변수를 만든다.
노드를 받아서 처리하는 헬퍼 함수를 만든다:
- 다음으로, left가 있다면 left 노드를 헬퍼 함수로 실행한다.
- 이 함수는 그리고 노드의 값을 저장하는 변수에 값을 저장한다.
- right가 있다면 right 노드를 헬퍼 함수로 실행한다.
루트를 헬퍼 함수로 실행한다.

javascript
DFSInOrder(){
  const data = [];
  function traverse(node){
    if(node.left) traverse(node.left);
    data.push(node.value); // PreOrder, PostOrder와 비교하면 여기만 다르다!
    if(node.right) traverse(node.right);
  }
  traverse(this.root);
  return data;
}

BinarySearchTree.DFSInOrder(); // [3, 6, 8, 10, 15, 20]

BFS vs DFS

알고리즘에서 늘 그렇듯이 둘 중 뭐가 낫느냐는 상황에 따라 다르다. BFS와 DFS는 모두 시간 복잡도 측면에선 O(V+E)로, 여기서 V는 정점(Vertex)의 수, E는 간선(Edge)의 수다. 모든 노드를 한번씩 방문한다는 점에서 시간 복잡도가 동일하다.

다만, 공간 복잡도 측면에선 트리의 형태에 따라 다르다. DFS는 스택 기반이기에, 트리의 깊이만큼 스택이 필요하다. 반면, BFS는 큐 기반이기에 트리의 너비만큼의 노드를 큐에 저장해야 한다. 아래의 균형잡힌 이진 트리를 예로 들어보자.

bash
        1
     /     \
    2       3
   / \     / \
  4   5   6   7

균형잡힌 이진 트리에서 트리의 높이는 log n, 너비는 n/2이다. 따라서 DFS가 공간 복잡도 측면에서 보다 유리하다.

하지만 늘 DFS가 유리한건 아니다. 아래의 가느다란 편향 트리(Skewed Tree)의 예를 살펴보자.

높이는 n인 반면, 너비는 1에 불과하다. 이 경우, DFS는 깊이만큼 재귀를 하는 반면 BFS는 항상 최대 1~2개 노드만 큐에 저장한다. 즉, O(1)로 매우 공간 복잡도가 낮다.

DFS 안에서는 어떤 방식을 써야할까? 이것 역시 상황에 따라 다르지만, InOrder는 반환 값이 정렬된 값이다. PreOrder는 루트 노드가 항상 맨 앞에 있으므로 나중에 다시 해당 트리를 만든다거나 루트 노드를 찾을때 아주 편리하다.

🤠 개인 탐구

프로그래머스는 코딩테스트 고득점 Kit 카테고리에 DFS/BFS 문제 7개를 제공한다. 이 문제들을 풀어보면서 복습하고자 한다.

1. 타겟 넘버(Lv.2)

이 문제는 n개의 음이 아닌 정수들에 대해, 순서를 바꾸지 않고 더하거나 빼기만 해서 타겟 넘버를 만드는 방법의 수를 구하는 문제다. 즉, 각 수들 사이에 + 또는 -하는 모든 경우의 수를 탐색해야 한다.

만약 numbers = [1, 1, 1]식으로 주어진다면 트리는 아래와 같은 형태일 것이다.

bash
              0
         +1       -1
       +2 -0     0  -2
     +3 +1 -1 -3 ...

이 문제는 DFS로도, BFS로도 풀 수 있다.

1-1. 타겟 넘버(DFS)

dfs라는 함수를 만들고 재귀적으로 해결하는 방식이다.

javascript
function solution(numbers, target){
  let count = 0;

  function dfs(index, sum){
    if(index === numbers.length){
      if(sum === target) count++;
      return;
    }

    dfs(index + 1, sum + numbers[index]);
    dfs(index + 1, sum - numbers[index]);
  }
  dfs(0, 0);
  return count;
}

참고로, 우리가 위에서 배운 DFSPreOrder로 구현하면 이렇게 된다:

javascript
function solution(numbers, target) {
    let answer = 0;

    let root = new BinarySearchTree();
    root.insert(0);
    numbers.forEach(function(val) {
       root.insert(val); 
    });

    answer = root.DFSPreOrder(target);
    return answer;
}

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }   
}
class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    insert(value) {
        let newNode = new Node(value);
        if(this.root === null) {
            this.root = newNode;
            return this;
        } else {
            let current = this.root;
            function traverse(node) {
                if(node.left) traverse(node.left);
                if(node.right) traverse(node.right);
                if(node.left === null) {
                    let leftNode = new Node(-value);
                    let rightNode = new Node(value);
                    node.left = leftNode;
                    node.right = rightNode;
                }
            }
            traverse(current);
            return this;
        }
    }
    DFSPreOrder(target) {
        let count = 0;
        let data = 0;
        let current = this.root;
        function traverse(node) {
            data = data + node.value;
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            if(node.left === null) {
                if(data === target) {
                    count++;
                }
            }
            data = data - node.value;
        }
        traverse(current);
        return count;
    }
}

1-2. 타겟 넘버(BFS)

BFS는 큐를 사용해서 모든 경우를 한 단계씩 확장하는 풀이다. 즉, 상태를 [현재까지의 합, 현재 인덱스] 쌍으로 저장하고 큐에 [0, 0]을 넣은 후(초기 합 0, 인덱스 0), 매 단계마다 +와 -를 선택한 경우를 큐에 추가한다. 인덱스가 numbers.length에 도달했을 때 합이 target이면 카운터를 1 증가시킨다.

javascript
function solution(numbers, target){
  let count = 0;
  const queue [[0, 0]];

  while(queue.length){
    const [sum, index] = queue.shift();

    if(index === numbers.length){
      if(sum === target) count++;
    } else {
      queue.push([sum + numbers[index], index + 1]);
      queue.push([sum - numbers[index], index + 1]);
    }
  }
  return count;
}

PreviousBinary Search Trees

Algorithm

NextBinary Heaps

Algorithm