icon

안동민 개발노트

5장: 트리와 이진 탐색 트리

트리 순회와 재귀적 사고

트리 순회는 노드를 어떤 순서로 방문할지 정하는 규칙입니다. 전위/중위/후위라는 이름보다, 현재 노드를 언제 기록하느냐가 더 중요합니다. 이 원리 하나만 잡아도 순회 문제가 훨씬 단순해집니다.

이름은 기억나는데 문제에 적용이 안 되는 경우가 많습니다. 그래서 여기서는 암기보다 요구사항에 맞는 방문 시점 고르기에 집중합니다. 같은 트리를 다른 순서로 처리해 결과가 어떻게 바뀌는지 바로 보이게 구성했습니다.

핵심 개념 정돈

트리 순회는 이름보다 현재 노드를 언제 기록하느냐를 우선 보면 빠르게 정리됩니다. 지금 문제를 보고 결과에 값을 넣는 시점을 우선 한 문장으로 적어 보세요.

방문 시점은 현재 노드 값을 결과에 넣는 타이밍입니다. 재귀 프레임에서 현재 노드를 왼쪽 처리 전/사이/후 어디서 기록하는지로 순회 종류가 갈립니다. 현재를 우선 기록하면 전위, 왼쪽을 끝낸 뒤 기록하면 중위가 됩니다.

재귀 순회는 같은 방문 규칙을 자식 서브트리에 반복 적용하는 구현입니다. 함수 호출 스택이 자동으로 진행 상태를 보관해 주기 때문에 코드가 짧고 읽기 쉽습니다. dfs(node.left)와 dfs(node.right) 사이에 기록 코드를 두면 중위 순회가 됩니다.

반복 순회는 스택/큐로 상태를 직접 들고 가는 방식입니다. 명시적 자료구조에 미방문 노드와 진행 단계를 저장해 재귀 동작을 수동으로 재현합니다. 중위 순회는 왼쪽 끝까지 스택에 넣고, pop하면서 값을 기록한 뒤 오른쪽으로 이동합니다.

트리 순회 전략이 실무에서 중요한 이유

순회 시점을 잘못 선택하면 문제 요구와 결과가 어긋납니다.
예를 들어 BST를 정렬 순서로 출력해야 하는데 전위 순회를 쓰면 오답입니다.

또한 대형 트리에서는 재귀 깊이와 스택 안전성을 고려해야 합니다.
순회는 기능뿐 아니라 운영 안정성까지 함께 설계해야 하는 요소입니다.

순회 누락 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

아래 트리에서 방문 시점만 바뀌는 것을 직접 확인해 봅니다.

  • 트리: 루트 1, 왼쪽 2(4,5), 오른쪽 3
  • 목표: 전위/중위/후위 순회 결과 비교
  1. 전위는 현재 노드를 우선 기록해 1 2 4 5 3이 됩니다.
  2. 중위는 왼쪽 처리 후 현재를 기록해 4 2 5 1 3이 됩니다.
  3. 후위는 자식 처리 후 현재를 기록해 4 5 2 3 1이 됩니다.

트리 순회: 재귀 순회 3종

문제 의도: 같은 트리를 전위/중위/후위로 순회하며 기록 시점 차이를 확인합니다.
입력 예시: 1(2(4,5),3) 형태 이진 트리
출력 예시: 전위 [1,2,4,5,3], 중위 [4,2,5,1,3], 후위 [4,5,2,3,1] out.append/push_back/push는 현재 방문한 값을 결과에 기록하는 공통 동작입니다.

main.cpp
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

void preorder(Node* node, vector<int>& out) {
    if (!node) return;
    out.push_back(node->val);
    preorder(node->left, out);
    preorder(node->right, out);
}

void inorder(Node* node, vector<int>& out) {
    if (!node) return;
    inorder(node->left, out);
    out.push_back(node->val);
    inorder(node->right, out);
}

void postorder(Node* node, vector<int>& out) {
    if (!node) return;
    postorder(node->left, out);
    postorder(node->right, out);
    out.push_back(node->val);
}

int main() {
    Node* root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    vector<int> a, b, c;
    preorder(root, a);
    inorder(root, b);
    postorder(root, c);
    for (int x : a) cout << x << " ";
    cout << "\n";
    for (int x : b) cout << x << " ";
    cout << "\n";
    for (int x : c) cout << x << " ";
    cout << "\n";
    return 0;
}
Main.java
import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
        Node(int val, Node left, Node right) {
            this.val = val; this.left = left; this.right = right;
        }
    }

    static void preorder(Node node, List<Integer> out) {
        if (node == null) return;
        out.add(node.val);
        preorder(node.left, out);
        preorder(node.right, out);
    }

    static void inorder(Node node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    static void postorder(Node node, List<Integer> out) {
        if (node == null) return;
        postorder(node.left, out);
        postorder(node.right, out);
        out.add(node.val);
    }

    public static void main(String[] args) {
        Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
        List<Integer> a = new ArrayList<>(), b = new ArrayList<>(), c = new ArrayList<>();
        preorder(root, a);
        inorder(root, b);
        postorder(root, c);
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}
main.py
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(node, out):
    if node is None:
        return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)

root = Node(1, Node(2, Node(4), Node(5)), Node(3))
a, b, c = [], [], []
preorder(root, a)
inorder(root, b)
postorder(root, c)
print(a)  # [1, 2, 4, 5, 3]
print(b)  # [4, 2, 5, 1, 3]
print(c)  # [4, 5, 2, 3, 1]
main.rs
#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }
}

fn preorder(node: &Option<Box<Node>>, out: &mut Vec<i32>) {
    if let Some(n) = node {
        out.push(n.val);
        preorder(&n.left, out);
        preorder(&n.right, out);
    }
}

fn inorder(node: &Option<Box<Node>>, out: &mut Vec<i32>) {
    if let Some(n) = node {
        inorder(&n.left, out);
        out.push(n.val);
        inorder(&n.right, out);
    }
}

fn postorder(node: &Option<Box<Node>>, out: &mut Vec<i32>) {
    if let Some(n) = node {
        postorder(&n.left, out);
        postorder(&n.right, out);
        out.push(n.val);
    }
}

fn main() {
    let mut root = Node::new(1);
    let mut left = Node::new(2);
    left.left = Some(Box::new(Node::new(4)));
    left.right = Some(Box::new(Node::new(5)));
    root.left = Some(Box::new(left));
    root.right = Some(Box::new(Node::new(3)));
    let root = Some(Box::new(root));

    let mut a = Vec::new();
    let mut b = Vec::new();
    let mut c = Vec::new();
    preorder(&root, &mut a);
    inorder(&root, &mut b);
    postorder(&root, &mut c);
    println!("{:?}", a);
    println!("{:?}", b);
    println!("{:?}", c);
}

트리 순회 동작 트리 구조 조건 검토

세 함수의 구조는 동일하고 append 위치만 다릅니다.
이 구조적 일관성을 이해하면 변형 문제를 빠르게 구현할 수 있습니다.
중위 순회는 BST에서 정렬 결과를 만들기 때문에 실무에서도 자주 활용됩니다.

  • 평균 시간복잡도: O(N)
  • 최악 시간복잡도: O(N)
  • 공간복잡도: O(H) (H는 트리 높이)

트리 순회: 반복 중위 순회

문제 의도: 재귀 없이 스택으로 중위 순회를 구현해 스택 상태 전개를 이해합니다.
입력 예시: 1(2(4,5),3)
출력 예시: [4,2,5,1,3] 반복 구현에서는 cur가 현재 노드, stack이 돌아올 경로를 저장하는 역할입니다.

main.cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

vector<int> inorderIterative(Node* root) {
    stack<Node*> st;
    Node* cur = root;
    vector<int> out;

    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        out.push_back(cur->val);
        cur = cur->right;
    }
    return out;
}

int main() {
    Node* root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    auto out = inorderIterative(root);
    for (int x : out) cout << x << " ";
    cout << "\n";
    return 0;
}
Main.java
import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
        Node(int val, Node left, Node right) {
            this.val = val; this.left = left; this.right = right;
        }
    }

    static List<Integer> inorderIterative(Node root) {
        Deque<Node> stack = new ArrayDeque<>();
        Node cur = root;
        List<Integer> out = new ArrayList<>();

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            out.add(cur.val);
            cur = cur.right;
        }
        return out;
    }

    public static void main(String[] args) {
        Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
        System.out.println(inorderIterative(root));
    }
}
main.py
def inorder_iterative(root):
    stack = []
    cur = root
    out = []

    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left

        cur = stack.pop()
        out.append(cur.val)
        cur = cur.right

    return out

print(inorder_iterative(root))  # [4, 2, 5, 1, 3]
main.rs
#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }
}

fn inorder_iterative(root: &Option<Box<Node>>) -> Vec<i32> {
    let mut stack: Vec<&Node> = Vec::new();
    let mut cur = root.as_deref();
    let mut out = Vec::new();

    while cur.is_some() || !stack.is_empty() {
        while let Some(node) = cur {
            stack.push(node);
            cur = node.left.as_deref();
        }
        let node = if let Some(node) = stack.pop() {
            node
        } else {
            break;
        };
        out.push(node.val);
        cur = node.right.as_deref();
    }
    out
}

fn main() {
    let mut root = Node::new(1);
    let mut left = Node::new(2);
    left.left = Some(Box::new(Node::new(4)));
    left.right = Some(Box::new(Node::new(5)));
    root.left = Some(Box::new(left));
    root.right = Some(Box::new(Node::new(3)));
    let root = Some(Box::new(root));

    println!("{:?}", inorder_iterative(&root));
}

트리 순회 동작 순회 상태 추적

반복 구현은 재귀 호출 스택을 명시적 스택으로 옮긴 형태입니다.
깊은 트리에서도 재귀 한계에 덜 민감해 운영 안정성이 좋습니다.
다만 상태 변수(cur, stack)가 늘어나므로 구현 실수를 주의해야 합니다.

  • 평균 시간복잡도: O(N)
  • 최악 시간복잡도: O(N)
  • 공간복잡도: O(H)

트리 순회: 레벨 순회(BFS)

문제 의도: 큐를 사용해 트리를 레벨 단위로 방문하는 BFS 순회를 구현합니다.
입력 예시: 1(2(4,5),3)
출력 예시: [[1],[2,3],[4,5]] 큐에 넣을 때가 다음에 방문할 후보 등록, 꺼낼 때가 실제 방문입니다.

main.cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

vector<vector<int>> levelOrder(Node* root) {
    if (!root) return {};
    queue<Node*> q;
    q.push(root);
    vector<vector<int>> levels;

    while (!q.empty()) {
        int size = static_cast<int>(q.size());
        vector<int> level;
        for (int i = 0; i < size; ++i) {
            Node* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        levels.push_back(level);
    }
    return levels;
}

int main() {
    Node* root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    auto levels = levelOrder(root);
    for (auto& lv : levels) {
        cout << "[";
        for (int i = 0; i < static_cast<int>(lv.size()); ++i) {
            if (i) cout << ", ";
            cout << lv[i];
        }
        cout << "] ";
    }
    cout << "\n";
    return 0;
}
Main.java
import java.util.*;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
        Node(int val, Node left, Node right) {
            this.val = val; this.left = left; this.right = right;
        }
    }

    static List<List<Integer>> levelOrder(Node root) {
        if (root == null) return new ArrayList<>();
        Deque<Node> q = new ArrayDeque<>();
        q.addLast(root);
        List<List<Integer>> levels = new ArrayList<>();

        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node node = q.removeFirst();
                level.add(node.val);
                if (node.left != null) q.addLast(node.left);
                if (node.right != null) q.addLast(node.right);
            }
            levels.add(level);
        }
        return levels;
    }

    public static void main(String[] args) {
        Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
        System.out.println(levelOrder(root)); // [[1], [2, 3], [4, 5]]
    }
}
main.py
def level_order(root):
    if root is None:
        return []

    q = [root]
    head = 0
    levels = []

    while head < len(q):
        size = len(q) - head
        cur_level = []

        for _ in range(size):
            node = q[head]
            head += 1
            cur_level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

        levels.append(cur_level)

    return levels

print(level_order(root))  # [[1], [2, 3], [4, 5]]
main.rs
#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }
}

fn level_order(root: &Option<Box<Node>>) -> Vec<Vec<i32>> {
    let mut levels = Vec::new();
    if root.is_none() {
        return levels;
    }

    let mut q: Vec<&Node> = Vec::new();
    let mut head: usize = 0;
    if let Some(node) = root.as_deref() {
        q.push(node);
    }

    while head < q.len() {
        let size = q.len() - head;
        let mut level = Vec::new();
        for _ in 0..size {
            let node = q[head];
            head += 1;
            level.push(node.val);
            if let Some(left) = node.left.as_deref() {
                q.push(left);
            }
            if let Some(right) = node.right.as_deref() {
                q.push(right);
            }
        }
        levels.push(level);
    }
    levels
}

fn main() {
    let mut root = Node::new(1);
    let mut left = Node::new(2);
    left.left = Some(Box::new(Node::new(4)));
    left.right = Some(Box::new(Node::new(5)));
    root.left = Some(Box::new(left));
    root.right = Some(Box::new(Node::new(3)));
    let root = Some(Box::new(root));

    println!("{:?}", level_order(&root));
}

트리 순회 동작 구조 수정 후 재확인

레벨 순회는 DFS 계열 순회와 달리 큐를 사용합니다.
레벨 단위 결과가 필요한 문제(최소 깊이, 레벨 평균)에 적합합니다.
같은 트리라도 요구 결과 형식에 따라 순회 전략이 달라져야 합니다.

  • 시간복잡도: O(N)
  • 공간복잡도: O(N)

트리 높이/분기수 입력 분포 기준

순회 선택은 출력 요구를 기준으로 판단합니다.

  • 루트 우선 처리: 전위
  • 정렬/중간 처리: 중위
  • 하위 계산 후 결합: 후위
  • 레벨 단위 처리: BFS 레벨 순회

문제 문장에서 요구하는 결과 모양을 우선 읽으면 선택 오류가 줄어듭니다.

재귀 순회와 반복 순회 구현 비용 상충

순회 구현 방식의 균형점입니다.

  • 재귀: 코드 간결, 깊이 제한 위험
  • 반복: 깊이 안전, 상태 관리 복잡
  • BFS: 레벨 처리 강점, 큐 메모리 사용 증가

트리 높이와 출력 형식을 함께 고려해 구현 방식을 정해야 합니다.

순회 로그로 보는 실수 포인트

트리 순회에서 자주 틀리는 지점입니다.

  • 종료 조건 누락으로 None 접근 오류
  • 전역 리스트 재사용으로 테스트 오염
  • 반복 구현에서 stack pop 시점 오류
  • 편향 트리 입력에서 재귀 깊이 한계 초과

반례 테스트는 완전 이진 트리뿐 아니라 편향 트리를 반드시 포함해야 합니다.

순회 연산 비용 모델 정리

입력 분포가 치우치면 같은 알고리즘이라도 성능 체감이 달라지므로, 선택 관점을 데이터 특성과 함께 기록해 두는 편이 안전합니다.

순회평균 시간최악 시간공간
전위/중위/후위(DFS)O(N)O(N)O(H)
레벨 순회(BFS)O(N)O(N)O(W) (W는 최대 폭)

시간복잡도는 같아도 메모리 사용 패턴이 다르므로 문제 특성에 맞춰 선택해야 합니다.

순회 누락 실패사례 검토 포인트

  • 순회 결과를 저장할지 즉시 처리할지에 따라 메모리 사용량이 달라집니다.
  • 트리 노드가 매우 큰 객체면 순회 중 참조 유지 비용을 고려해야 합니다.
  • 재귀/반복 구현을 혼합할 때 상태 변수 의미를 명확히 분리해야 합니다.
  • 디버깅 시 방문 순서 로그를 짧게 출력하면 오류 위치를 빠르게 찾을 수 있습니다.

트리 순회 구현 점검 목록

  • 문제 요구에 맞는 방문 시점(전위/중위/후위)을 선택했는가
  • 재귀 깊이가 입력 제한을 넘지 않는지 확인했는가
  • 반복 구현 시 스택 push/pop 순서를 검증했는가
  • 레벨 순회에서 레벨 경계를 큐 크기로 정확히 처리했는가

트리 순회 학습 정리

트리 순회의 본질은 방문 시점 설계입니다.
시점과 상태 전개를 정확히 이해하면, 대부분의 트리 문제를 안정적으로 패턴화할 수 있습니다.

해시 사용 시 성능과 보안 상충 지점

이전 페이지

BST 삽입, 삭제, 탐색의 핵심 규칙

다음 페이지

목차

핵심 개념 정돈
트리 순회 전략이 실무에서 중요한 이유
순회 누락 오답 재현으로 검증하기
트리 순회: 재귀 순회 3종
트리 순회 동작 트리 구조 조건 검토
트리 순회: 반복 중위 순회
트리 순회 동작 순회 상태 추적
트리 순회: 레벨 순회(BFS)
트리 순회 동작 구조 수정 후 재확인
트리 높이/분기수 입력 분포 기준
재귀 순회와 반복 순회 구현 비용 상충
순회 로그로 보는 실수 포인트
순회 연산 비용 모델 정리
순회 누락 실패사례 검토 포인트
트리 순회 구현 점검 목록
트리 순회 학습 정리