[Hackerrank 문제 풀이] Binary Search Tree Insertion

Junu Kim·2025년 12월 7일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

52/89

[BST] Binary Search Tree Insertion

난이도: ★☆☆☆☆ • solved on: 2025-12-07

문제 요약

문제 유형: 이진 탐색 트리(BST), 재귀·반복 삽입
요구사항: 주어진 BST에 data 값을 삽입한 뒤 root 노드 전체를 반환해야 한다.

사용 개념

자료구조
- Node : data, left, right를 가지는 기본 트리 구조
알고리즘/기법
- BST 규칙:
  - data < node.data → 왼쪽 이동
  - data > node.data → 오른쪽 이동
- 재귀 또는 반복 기반 삽입
핵심 키워드
- BST property
- insertion
- traversal without modifying existing structure

풀이 아이디어 및 코드

방법 1: 반복문 기반 최초 풀이

문제 분해

root == null 인 경우 초기 트리를 만드는 상황이므로 new Node(data) 반환.

그렇지 않으면 currentNode 를 루트부터 따라 내려가며:

data > currentNode.data → 오른쪽으로 이동

data <= currentNode.data → 왼쪽으로 이동

해당 위치에 자식이 없으면 새 노드를 삽입하고 전체 트리의 root 반환.

핵심 로직 흐름

current = root
while (current != null):
    if data < current.data:
        왼쪽이 null이면 삽입 후 종료
        아니면 왼쪽으로 계속 이동
    else:
        오른쪽이 null이면 삽입 후 종료
        아니면 오른쪽으로 이동

코드

public static Node insert(Node root, int data) {
    if (root == null) {
        return new Node(data);
    }

    Node currentNode = root;

    while (currentNode != null) {
        if (currentNode.data < data) {
            if (currentNode.right == null) {
                currentNode.right = new Node(data);
                return root;
            }
            currentNode = currentNode.right;
            continue;
        }

        if (data <= currentNode.data) {
            if (currentNode.left == null) {
                currentNode.left = new Node(data);
                return root;
            }
            currentNode = currentNode.left;
            continue;
        }
    }
    return root;
}

예외 처리

초기 트리 생성 시(root == null)을 반드시 고려해야 한다.
빈 트리에서부터 삽입을 반복 호출하는 구조이므로 null 케이스 없으면 실패한다.

방법 2: 재귀 기반 풀이

재귀를 쓰면 코드를 크게 줄이면서 BST 삽입 규칙을 그대로 표현할 수 있다.

문제 분해

root == null이면 삽입 위치 도달 → new Node(data) 반환.
data < root.data → 왼쪽 서브트리에 삽입.
data > root.data → 오른쪽 서브트리에 삽입.
자식이 갱신된 root를 그대로 반환.

핵심 로직 흐름

if root == null → 새 노드 생성  
if data < root.data → root.left = insert(root.left, data)  
if data > root.data → root.right = insert(root.right, data)  
return root

코드

public static Node insert(Node root, int data) {

    if (root == null) {
        return new Node(data);
    }

    if (data <= root.data) {
        root.left = insert(root.left, data);
    } else {
        root.right = insert(root.right, data);
    }

    return root;
}