C#에서 반복문(Queue)으로 이진 트리의 대칭 여부 확인하는 방법

재귀 호출 없이 반복(Iterative) 방식으로 이진 트리가 좌우 대칭인지 판별하려면 두 개의 큐(Queue)를 활용하는 것이 핵심입니다. 한 큐에는 왼쪽 자식 노드를, 다른 큐에는 오른쪽 자식 노드를 저장한 뒤, 두 큐에서 노드를 꺼내며 짝지어 비교하는 구조입니다.

동작 원리

트리가 비어 있다면(null) 루트 노드를 기준으로 하는 수직 축에 대해 항상 대칭이라고 볼 수 있으므로 true를 반환합니다. 트리가 존재한다면 아래 순서대로 검사를 진행합니다.

루트 노드가 null이면 즉시 true를 반환합니다.
두 개의 큐를 생성하고, 첫 번째 큐(Q1)에는 루트의 왼쪽 자식을, 두 번째 큐(Q2)에는 루트의 오른쪽 자식을 삽입합니다.
두 큐가 모두 빌 때까지 반복하면서 각 큐에서 노드를 하나씩 꺼냅니다(dequeue).
한쪽 노드만 null이면 대칭이 아니므로 false를 반환합니다.
두 노드 모두 null이 아니라면 값(Value)이 같은지 비교하고, 다르면 false를 반환합니다.
값이 같다면 자식 노드를 교차 방식으로 삽입합니다. Q1에는 왼쪽 자식 → 오른쪽 자식 순으로, Q2에는 오른쪽 자식 → 왼쪽 자식 순으로 넣어 좌우가 거울상처럼 만나도록 합니다.

예제 코드

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 bool IsSymmetricIterative(Node node){
        // 빈 트리는 항상 대칭
        if (node == null){
            return true;
        }

        Queue<Node> q1 = new Queue<Node>();
        Queue<Node> q2 = new Queue<Node>();

        q1.Enqueue(node.LeftChild);   // 왼쪽 서브트리
        q2.Enqueue(node.RightChild);  // 오른쪽 서브트리

        while (q1.Count > 0 && q2.Count > 0){
            Node n1 = q1.Dequeue();
            Node n2 = q2.Dequeue();

            // 한쪽만 null이면 구조가 비대칭
            if ((n1 == null && n2 != null) || (n1 != null && n2 == null)){
                return false;
            }

            if (n1 != null){
                // 값이 다르면 비대칭
                if (n1.Value != n2.Value){
                    return false;
                }

                // 교차 삽입: 좌↔우가 거울상으로 비교되도록 함
                q1.Enqueue(n1.LeftChild);
                q1.Enqueue(n1.RightChild);
                q2.Enqueue(n2.RightChild);
                q2.Enqueue(n2.LeftChild);
            }
        }
        return true;
    }
}

실행 결과

아래와 같은 대칭 구조의 트리를 입력하면 메서드는 true를 반환합니다.

정리

이 방식은 재귀 호출로 인한 스택 오버플로 위험 없이 BFS(너비 우선 탐색) 형태로 트리를 순회하기 때문에, 깊이가 매우 깊은 트리에서도 안전하게 대칭 여부를 검사할 수 있습니다. 시간 복잡도는 O(n), 공간 복잡도는 큐에 저장되는 노드 수에 비례하여 O(n)입니다.