[HackerRank] Binary Search Tree : Insertion

https://www.hackerrank.com/challenges/binary-search-tree-insertion/problem

Binary Search Tree : Insertion | HackerRank

Data Structures > Trees

 

이진 탐색 트리 삽입 문제다.

 

 

코드

struct node* insert( struct node* root, int data ) {
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    if (!root) return newNode;
    if (data > root->data)
        root->right = insert(root->right, data);
    if (data < root->data)
        root->left = insert(root->left, data);
    return root;
}

 

설명

새로운 노드(newNode)를 만들어 data에 data를 저장하고, left와 right를 null로 지정한다.

만약 주어진 이진 탐색 트리가 null이라면, 새로운 노드를 삽입했을 때 그 노드만 존재하므로 바로 newNode를 리턴한다.

이진 탐색 트리에 값이 존재하면 data끼리 비교하여 값이 크면 오른쪽, 값이 작으면 왼쪽을 탐색한다.

즉, 삽입하려는 data가 현재 탐색 중인 노드의 data보다 크면 노드의 오른쪽으로 범위를 재설정해 재귀호출하고,

작다면 노드의 왼쪽으로 범위를 재설정해 재귀호출한다.

이러한 과정을 통해 데이터는 비어 있는 적절한 자리에 삽입되고,

마지막에 root를 리턴함으로써 완성된 이진 탐색 트리가 반환된다.