JavaScript로 두 개의 BST에서 두 수의 합(Two Sum) 찾기

문제 개요

이번 글에서는 두 개의 이진 탐색 트리(Binary Search Tree, BST)가 주어졌을 때, 각 트리에서 하나씩 노드를 골라 그 값의 합이 목표값(target)과 일치하는지 판별하는 JavaScript 함수를 작성하는 방법을 알아보겠습니다.

함수는 두 BST의 루트 노드인 root1과 root2를 각각 첫 번째, 두 번째 인수로 받고, 세 번째 인수로 숫자 target을 받습니다.

함수는 첫 번째 트리의 어떤 노드와 두 번째 트리의 어떤 노드의 값 합이 주어진 정수 target과 같아지는 경우가 존재할 때만 true를 반환하고, 그렇지 않으면 false를 반환해야 합니다.

입력 예시

const target = 23;

BST 구조

출력

const output = true;

출력 설명

첫 번째 트리에는 6이라는 값이, 두 번째 트리에는 17이라는 값이 존재하며, 6 + 17 = 23이므로 목표값과 일치하는 노드 쌍이 있습니다. 따라서 결과는 true입니다.

알고리즘 동작 원리

이 풀이는 BST의 핵심 특성, 즉 "왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다"는 규칙을 활용합니다. 두 트리를 동시에 재귀적으로 탐색하면서 현재 노드 값의 합을 target과 비교하는 방식입니다.

• 합이 target과 같으면: 조건을 만족하는 노드 쌍을 찾은 것이므로 즉시 true를 반환합니다.
• 합이 target보다 작으면: 더 큰 값이 필요하므로, 첫 번째 트리의 오른쪽 서브트리 또는 두 번째 트리의 오른쪽 서브트리를 탐색합니다.
• 합이 target보다 크면: 더 작은 값이 필요하므로, 첫 번째 트리의 왼쪽 서브트리 또는 두 번째 트리의 왼쪽 서브트리를 탐색합니다.

탐색 도중 어느 한쪽 트리라도 null에 도달하면 해당 경로에는 답이 존재하지 않으므로 false를 반환합니다. 전체 시간 복잡도는 O(n1 × n2)이며, n1과 n2는 각 트리의 노드 개수입니다.

구현 코드

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 tree1 = new BinarySearchTree();
tree1.insert(1);
tree1.insert(3);
tree1.insert(4);
tree1.insert(2);
tree1.insert(4);
tree1.insert(5);
tree1.insert(6);
const tree2 = new BinarySearchTree();
tree2.insert(9);
tree2.insert(6);
tree2.insert(11);
tree2.insert(3);
tree2.insert(8);
tree2.insert(10);
tree2.insert(17);
const twoSumBSTs = (root1, root2, target) => {
   if(root1 == null || root2 == null) return false;
   if(root1.data + root2.data == target) return true;
   if(root1.data + root2.data < target) {
      return twoSumBSTs(root1.right, root2, target) || twoSumBSTs(root1, root2.right, target);
   }else{
      return twoSumBSTs(root1.left, root2, target) || twoSumBSTs(root1,
      root2.left, target);
   };
};
const target = 23;
console.log(twoSumBSTs(tree1.root, tree2.root, target));

실행 결과

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

true