문제 개요
이진 탐색 트리(Binary Search Tree, BST)의 루트 노드를 유일한 인수로 받아, 왼쪽 리프(left leaf) 노드에 저장된 값들의 합을 계산하는 자바스크립트 함수를 작성해 보겠습니다.
여기서 '왼쪽 리프'란 부모 노드의 왼쪽 자식이면서 동시에 자신은 자식 노드가 없는(리프) 노드를 의미합니다.
예시
다음과 같은 형태의 트리가 있다고 가정해 봅시다.
8
/ \
1 10
/ \
5 17
이때 기대하는 출력 결과는 다음과 같습니다.
const output = 6;
출력 설명
위 트리에서 왼쪽 리프 노드는 값이 1(노드 8의 왼쪽 자식)과 5(노드 10의 왼쪽 자식)인 두 노드입니다. 반면 17은 오른쪽 자식에 해당하므로 합산 대상에서 제외됩니다. 따라서 1 + 5 = 6이 반환됩니다.
구현 접근 방법
먼저 노드와 이진 탐색 트리를 나타내는 클래스를 정의한 뒤, 트리를 재귀적으로 순회하면서 왼쪽 리프 노드의 값만 더하는 방식으로 문제를 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.
- 현재 노드가 리프인지 판별하는 헬퍼 함수
isLeaf를 정의합니다. - 어떤 노드의 왼쪽 자식이 리프라면 그 값을 합계에 더합니다.
- 오른쪽 자식은 리프라 하더라도 합산하지 않으며, 단순히 계속 탐색만 진행합니다.
예제 코드
전체 구현 코드는 다음과 같습니다.
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};
class BinarySearchTree{
constructor(){
// 이진 탐색 트리의 루트
this.root = null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left = newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right = newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(6);
BST.insert(9);
BST.insert(4);
BST.insert(7);
const isLeaf = node => {
if (!node) return false;
return (node.left === null && node.right === null);
}
const traverseTreeAndSumLeftLeaves = (root, sum = 0) => {
if (!root) return sum;
if (isLeaf(root)) return sum;
if (root.left) {
if (isLeaf(root.left)) {
sum += root.left.data;
traverseTreeAndSumLeftLeaves(root.left, sum);
} else sum = traverseTreeAndSumLeftLeaves(root.left, sum);
}
if (root.right) {
if (isLeaf(root.right)) return sum;
else {
sum = traverseTreeAndSumLeftLeaves(root.right, sum);
}
}
return sum;
};
console.log(traverseTreeAndSumLeftLeaves(BST.root));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
7
예제 코드에서는 삽입된 값(5, 3, 6, 6, 9, 4, 7)으로 트리를 구성하기 때문에 위 그림과는 다른 트리가 만들어집니다. 이 트리에서 유일하게 조건을 만족하는 왼쪽 리프 노드는 값이 7인 노드이므로 결과가 7로 출력됩니다.
복잡도 분석
이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 재귀 호출 스택 깊이에 의해 결정되며, 편향된 트리의 경우 최악 O(n), 균형 잡힌 트리의 경우 O(log n)입니다.