C#에서 재귀를 활용해 이진 탐색 트리 반전하는 방법

개요

이진 탐색 트리(Binary Search Tree)를 반전(invert)한다는 것은 트리의 모든 노드에 대해 왼쪽 자식과 오른쪽 자식의 위치를 서로 바꿔, 원본 트리의 거울상(mirror image)을 만드는 것을 의미합니다.

이 작업은 재귀(Recursion)를 활용하면 매우 간결하게 구현할 수 있습니다. 동작 순서는 다음과 같습니다.

1. InvertABinarySearchTree 메서드를 호출하며 노드를 매개변수로 전달합니다.
2. 노드가 null이면 그대로 null을 반환합니다. 이것이 재귀 호출의 종료 조건(base case)입니다.
3. 노드가 null이 아니라면, 왼쪽 자식과 오른쪽 자식을 각각 인자로 전달하며 메서드를 재귀적으로 호출합니다.
4. 재귀 호출의 반환값을 서로 교차하여 대입합니다. 즉, 오른쪽 자식의 결과를 왼쪽에, 왼쪽 자식의 결과를 오른쪽에 할당합니다.

모든 재귀 호출이 완료되면 최종 출력은 자기 자신의 거울상이 된 트리입니다.

예제 코드

public class TreesPgm {
    public class Node {
        public int Value;
        public Node LeftChild;
        public Node RightChild;

        public Node(int value) {
            this.Value = value;
        }

        public override String ToString() {
            return "Node=" + Value;
        }
    }

    public Node InvertABinarySearchTree(Node node) {
        if (node == null) {
            return null;
        }
        Node left = InvertABinarySearchTree(node.LeftChild);
        Node right = InvertABinarySearchTree(node.RightChild);
        node.LeftChild = right;
        node.RightChild = left;
        return node;
    }
}

위 코드에서 재귀 호출이 먼저 리프 노드까지 내려간 뒤, 돌아오는 과정에서 각 노드의 자식들이 교환됩니다. 따라서 트리 전체가 아래에서부터 위로 뒤집히게 됩니다.

입력

    1
  3   2

루트 노드 1의 왼쪽 자식은 3, 오른쪽 자식은 2인 트리입니다.

출력

    1
  2   3

반전 후에는 루트 노드 1의 왼쪽 자식이 2, 오른쪽 자식이 3으로 바뀌어, 입력 트리의 거울상이 완성됩니다.