다음과 같은 형태의 이진 트리가 주어져 있다고 가정해 보겠습니다.
4
/ \
2 7
/ \ / \
1 3 6 9
우리가 작성해야 할 것은 이 이진 트리의 루트(root) 노드를 인자로 받아, 트리 전체를 좌우로 반전(뒤집기)하는 JavaScript 함수입니다.
위 트리를 반전하면 다음과 같은 형태가 됩니다.
4
/ \
7 2
/ \ / \
9 6 3 1
반전 로직의 핵심 원리
이진 트리 반전의 핵심 아이디어는 매우 간단합니다. 모든 노드에 대해 왼쪽 자식과 오른쪽 자식을 서로 맞바꾸는 작업을 재귀적으로 수행하면 됩니다.
JavaScript의 구조 분해 할당(Destructuring Assignment) 문법을 활용하면 임시 변수 없이 한 줄로 두 자식 노드를 교환할 수 있습니다.
[node.left, node.right] = [node.right, node.left];
전체 구현 코드
// 단일 트리 노드를 위한 클래스
class Node{
constructor(val){
this.val = val;
this.left = null;
this.right = null;
};
};
// 이진 트리를 위한 클래스
class BinaryTree{
constructor(){
// 이진 트리의 루트
this.root = null;
};
insert = (data) => {
// 데이터로 새 노드 생성
const newNode = new Node(data);
// 루트가 null이면 이 노드가 루트가 됨
if(this.root === null){
this.root = newNode;
}else{
// 그렇지 않으면 올바른 삽입 위치를 찾아 삽입
this.insertData(this.root, newNode);
};
};
insertData = (node, newNode) => {
if(newNode.val < node.val){
if(node.left === null){
node.left = newNode;
}else{
this.insertData(node.left, newNode);
}
}else{
if(node.right === null){
node.right = newNode;
}else{
this.insertData(node.right, newNode);
}
}
};
// 이진 트리를 반전하는 함수
invert = (node) => {
if(node === null){
return;
};
// 왼쪽과 오른쪽 자식을 맞바꿈
[node.left, node.right] = [node.right, node.left];
this.invert(node.right);
this.invert(node.left);
}
// 트리를 순회하며 값 출력
traverse = (node) => {
if(node === null){
return;
};
this.traverse(node.right);
console.log(node.val);
this.traverse(node.left);
};
};
const Tree = new BinaryTree();
Tree.insert(2);
Tree.insert(7);
Tree.insert(4);
Tree.insert(1);
Tree.insert(9);
Tree.insert(3);
Tree.insert(6);
// 원본 트리를 오른쪽에서 왼쪽으로 순회
Tree.traverse(Tree.root);
Tree.invert(Tree.root);
console.log('after inversion');
// 반전 후 오른쪽에서 왼쪽으로 순회
Tree.traverse(Tree.root);
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
9
7
6
4
3
2
1
after inversion
1
2
3
4
6
7
9
동작 방식 정리
invert 함수는 다음 순서로 동작합니다.
1. 현재 노드가 null이면 즉시 반환하여 재귀를 종료합니다.
2. 구조 분해 할당으로 현재 노드의 왼쪽 자식과 오른쪽 자식을 맞바꿉니다.
3. 바뀐 오른쪽 하위 트리와 왼쪽 하위 트리에 대해 각각 재귀 호출을 수행합니다.
이 과정을 통해 트리의 모든 노드가 방문되면서 좌우가 대칭으로 뒤집히게 됩니다. 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 공간 복잡도는 재귀 호출 스택의 깊이에 따라 최악의 경우 O(n), 균형 잡힌 트리라면 O(log n)입니다.