자바스크립트로 유니밸류(Univalued) 이진 탐색 트리 판별하기

유니밸류(Univalued) 이진 탐색 트리란?

이진 탐색 트리(Binary Search Tree, BST)를 구성하는 모든 노드가 동일한 값을 가질 때, 해당 트리를 유니밸류(Univalued) 트리라고 부릅니다. 즉, 루트부터 리프 노드까지 트리 전체의 데이터 값이 하나의 값으로 통일되어 있어야 합니다.

문제 정의

이번 문제에서는 이진 탐색 트리의 루트(root) 노드를 인수로 받아, 트리가 유니밸류인 경우에만 true를 반환하고 그렇지 않으면 false를 반환하는 자바스크립트 함수를 작성해야 합니다.

예를 들어, 트리의 노드 값이 다음과 같다고 가정해 보겠습니다.

const input = [5, 5, 5, 3, 5, 6];

이 배열에는 5 외에도 3과 6이라는 서로 다른 값이 포함되어 있으므로, 기대하는 출력 결과는 다음과 같습니다.

const output = false;

구현 예제

먼저 노드(Node) 클래스와 이진 탐색 트리(BinarySearchTree) 클래스를 정의하고 삽입(insert) 로직을 구현합니다. 이후 재귀 방식의 깊이 우선 탐색(DFS)으로 트리를 순회하면서, 모든 노드의 값이 루트의 값과 일치하는지 검사하는 isUnivalued 함수를 작성합니다.

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(5);
BST.insert(5);
BST.insert(3);
BST.insert(5);
BST.insert(6);
const isUnivalued = (root) => {
    const helper = (node, prev) => {
        if (!node) {
            return true
        }
        if (node.data !== prev) {
            return false
        }
        let isLeftValid = true
        let isRightValid = true
        if (node.left) {
            isLeftValid = helper(node.left, prev)
        }
        if (isLeftValid && node.right) {
            isRightValid = helper(node.right, prev)
        }
        return isLeftValid && isRightValid
    }
    if (!root) {
        return true
    }
    return helper(root, root.data)
};
console.log(isUnivalued(BST.root));

출력 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

false

동작 원리

isUnivalued 함수는 내부의 헬퍼(helper) 함수를 통해 깊이 우선 탐색을 수행합니다. 각 노드를 방문할 때마다 현재 노드의 값이 루트의 값(prev)과 일치하는지 비교하며, 값이 하나라도 다른 노드가 발견되면 즉시 false를 반환합니다.

특히 왼쪽 서브트리에서 이미 false가 반환된 경우에는 오른쪽 서브트리를 더 이상 탐색하지 않으므로, 불필요한 연산을 줄여 효율성을 높일 수 있습니다. 또한 트리가 비어 있는 경우(null)에는 관례적으로 true로 처리합니다. 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)입니다.