3주차 문제를 처음 만나다#

3주차 문제를 처음 봤을 때 나온 것은 이진트리 문제였다.

그런데 당시에는 ‘트리’라는 단어 자체를 몰랐다.

내가 알고 있는 트리라고는 크리스마스 트리뿐…

그래서 문제를 풀기 전에 트리가 무엇인지부터, 그리고 이진트리가 무엇인지까지 공부하게 됐다.

트리가 뭘까?#

트리는 나무처럼 여러 개의 노드가 연결되어 있는 계층적인 자료구조라고 생각하면 된다.

트리에는 여러 가지 용어가 있는데 하나씩 알아보자.

노드와 간선#

먼저 노드(Node)는 데이터를 담고 있는 하나의 요소라고 생각하면 된다.

그리고 노드와 노드를 연결하는 선을 간선(Edge)이라고 한다.

그림에서 동그라미 하나하나가 노드이고, 노드를 연결하는 선이 간선이다.

루트#

루트(Root)는 트리에서 가장 위에 있는 노드이다.

일반적인 트리에서는 루트가 하나만 존재한다.

리프#

트리의 가장 아래쪽에 있으면서 자식 노드가 없는 노드를 리프(Leaf)라고 한다.

부모와 자식#

어떤 노드와 연결되어 있을 때, 위쪽에 있는 노드를 부모(Parent)라고 하고 아래쪽에 연결된 노드를*자식(Child)이라고 한다.

예를 들어 1번 노드 아래에 2번 노드가 있다면,

• 1은 2의 부모
• 2는 1의 자식

이라고 할 수 있다.

조상과 자손#

어떤 노드에서 위쪽으로 간선을 따라 올라가면서 만나는 모든 노드를 조상(Ancestor)이라고 한다.

반대로 어떤 노드에서 아래쪽으로 내려가면서 만나는 모든 노드를 자손(Descendant)이라고 한다.

레벨#

레벨(Level)은 루트에서 해당 노드까지 얼마나 떨어져 있는지를 나타낸다.

보통 루트를 0레벨로 시작하고, 간선을 하나 내려갈 때마다 레벨이 1씩 증가한다.

예를 들어,

• 루트 → 0레벨
• 루트의 자식 → 1레벨
• 그 자식의 자식 → 2레벨

이 된다.

이진트리에 대해#

그렇다면 이진트리(Binary Tree)는 무엇일까?

쉽게 말하면 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다.

그리고 두 자식은 보통 다음과 같이 구분한다.

• 왼쪽 자식(Left Child)
• 오른쪽 자식(Right Child)

여기서 중요한 점은 자식이 반드시 2개 있어야 하는 것은 아니다.

자식이 0개일 수도 있고, 1개일 수도 있고, 최대 2개까지 있을 수 있다.

완전 이진트리#

완전 이진트리(Complete Binary Tree)는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 오른쪽 순서로 빈틈없이 채워지는 형태의 이진트리이다.

그런데 왼쪽은 작고 오른쪽은 크다?#

처음 트리를 공부할 때 헷갈렸던 부분이 있었다.

“왼쪽 서브트리의 값은 작고, 오른쪽 서브트리의 값은 커야 한다.”

라는 조건이다.

하지만 이것은 모든 이진트리의 조건이 아니다.

이 조건은 이진 탐색 트리(Binary Search Tree, BST)의 특징이다.

일반적인 이진트리는 단순히 각 노드가 최대 2개의 자식을 가지는 것이 핵심이다.

이진 탐색 트리에서는 일반적으로 다음과 같은 규칙을 가진다.

• 왼쪽 서브트리의 키 값 < 현재 노드의 키 값
• 오른쪽 서브트리의 키 값 > 현재 노드의 키 값

이진트리 ⊃ 이진 탐색 트리 라고 생각하면 이해하기 쉽다.

트리 문제를 풀기 전에#

트리 문제에서는 먼저 노드가 어떻게 만들어져 있는지 이해하는 것이 중요했다.

이진트리의 노드는 보통 이런 형태로 만들 수 있다.

self.value = value      # 노드에 담긴 값

self.left = None        # 왼쪽 자식
self.right = None       # 오른쪽 자식

자식 노드가 없는 방향은 None으로 둔다.

그리고 left는 왼쪽 자식, right는 오른쪽 자식을 가리킨다.

예를 들어 다음과 같이 트리를 만들 수 있다.

root = Node(1)

root.left = Node(2)
root.right = Node(3)

root.left.left = Node(4)
root.left.right = Node(5)

위 코드를 그림으로 생각하면 다음과 같은 구조가 된다.

• root는 값이 1인 노드
• root.left는 값이 2인 노드
• root.right는 값이 3인 노드
• root.left.left는 값이 4인 노드
• root.left.right는 값이 5인 노드

가 된다.

여기서 처음 공부할 때 헷갈렸던 부분이 있었다.

root.left = Node(2)

에서 2는 “2번 노드”라는 뜻이 아니다.

Node(2)에서 2는 단순히 그 노드가 가지고 있는 값(value)이다.

노드 자체 ≠ 노드가 가지고 있는 값

이라고 생각하면 된다.

트리 순회#

트리에서 중요한 개념 중 하나가 순회(Traversal)이다.

순회란 트리의 모든 노드를 빠짐없이 한 번씩 방문하는 것이다.

대표적으로 다음 세 가지 순회 방법이 있다.

전위 순회#

루트 → 왼쪽 → 오른쪽

Root → Left → Right

중위 순회#

왼쪽 → 루트 → 오른쪽

Left → Root → Right

후위 순회#

왼쪽 → 오른쪽 → 루트

Left → Right → Root

이 세 가지 순회는 트리 문제에서 자주 등장하고, 특히 재귀를 이용하면 구조를 이해하기 쉽다.

이진트리 문제 풀기#

현재 다음과 같은 이진트리가 있다고 가정해보자.

        1
       / \
      2   3
     / \
    4   5

문제에서는 이 트리를 전위 순회하여 결과를 리스트로 반환해야 한다.

전위 순회는

루트 → 왼쪽 → 오른쪽

순서이므로 결과는

[1, 2, 4, 5, 3]

이 된다.

먼저 재귀 함수의 가장 중요한 부분부터 생각해보자.

def preorder(root):

    result = []

    if root is None:
        return []

여기서 root is None이라는 것은 현재 확인하려는 노드가 존재하지 않는다는 뜻이다.

더 이상 내려갈 노드가 없으므로 빈 리스트를 반환한다.

이 부분이 재귀에서 말하는 종료 조건(Base Case)이 된다.

1. 루트부터 결과에 추가하기#

전위 순회는

루트 → 왼쪽 → 오른쪽

순서이다.

따라서 가장 먼저 현재 노드의 값을 결과에 넣는다.

result = [root.value]

처음에는 루트가 1이므로,

result = [1]

이 된다.

2. 왼쪽 서브트리로 이동하기#

그다음에는 왼쪽으로 이동해야 한다.

preorder(root.left)

여기서 중요한 것은 preorder()가 파이썬에 원래 존재하는 전위 순회 함수라는 뜻이 아니다.

우리가 직접 만든 preorder() 함수를 다시 호출하는 것이다.

현재 노드가 1이라면,

preorder(root.left)

를 실행하면서 1의 왼쪽 노드인 2를 새로운 root로 가지고 다시 preorder()를 실행한다.

preorder(1)
    ↓
preorder(2)
    ↓
preorder(4)

처럼 트리를 따라 내려가게 된다.

그리고 4의 왼쪽을 확인했을 때 더 이상 노드가 없다면

if root is None:
    return []

에 의해 빈 리스트를 반환하고 다시 위로 돌아온다.

이런 식으로 재귀 함수가 스스로 같은 작업을 반복하면서 트리를 탐색한다.

3. 결과를 합치기#

왼쪽 서브트리를 순회한 결과를 현재 결과에 합쳐준다.

result = result + preorder(root.left)

처음 루트가 1일 때 생각해보면,

result
[1]

이고 왼쪽 서브트리인 2를 전위 순회하면

[2, 4, 5]

가 나온다.

따라서 둘을 합치면

[1] + [2, 4, 5]

= [1, 2, 4, 5]

가 된다.

그다음 오른쪽 서브트리도 같은 방법으로 처리한다.

result = result + preorder(root.right)

오른쪽 서브트리에서는

[3]

이 반환되므로 최종적으로

[1, 2, 4, 5] + [3]

= [1, 2, 4, 5, 3]

이 된다.

최종 코드#

전체 코드를 합치면 다음과 같다.

class TreeNode:
    """이진 트리 노드"""

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def preorder(root):
    """전위 순회: 루트 → 왼쪽 → 오른쪽"""

    # 현재 노드가 없다면 종료
    if root is None:
        return []

    # 루트 방문
    result = [root.value]

    # 왼쪽 서브트리 순회
    result = result + preorder(root.left)

    # 오른쪽 서브트리 순회
    result = result + preorder(root.right)

    return result

이 코드에서 가장 중요한 부분은 사실 세 줄이다.

result = [root.value]

result = result + preorder(root.left)

result = result + preorder(root.right)

전위 순회의 순서인

루트 → 왼쪽 → 오른쪽

을 코드로 그대로 옮긴 것이다.

그리고 preorder(root.left)와 preorder(root.right)를 다시 호출하는 부분이 바로 재귀이다.

처음에는 “함수가 자기 자신을 다시 호출한다”는 것이 굉장히 어렵게 느껴졌는데, 트리에서는 오히려 이 방식이 자연스럽다는 것을 알게 됐다.

현재 노드에서 왼쪽으로 내려가서 똑같은 일을 하고, 다시 돌아와서 오른쪽에서도 똑같은 일을 한다.

그래서 트리와 재귀가 잘 어울린다는 것을 조금 이해할 수 있었다.